IMA4 2016/2017 ECP4
Sommaire
Présentation du projet
Contexte
L'élève effectue son stage au Vietnam et dispose d'un PC. Une connexion Internet stable est disponible.
Objectif
l'objectif de ce projet est d'écrire une application Web de génération de chronogrammes d'ordonnancement de processsus. Les processus tournent sur un seul processeur mais peuvent réclamer et libérer des ressources.
Description du projet
Le projet comporte deux grandes parties :
- l'écriture de l'interface utilisateur pour décrire les processus à ordonnancer, pour choisir le type d'ordonnancement et pour afficher le chronogramme ;
- décliner les variantes possibles des différents algorithmes d'ordonnancement (fifo, tourniquet, priorité avec préemption, priorité avec âge et quantum de temps).
L'interface utilisateur doit être de type Web en HTML5. Il est bien entendu possible d'utiliser des bibliothèques JavaScript disponibles sur Internet. L'interface doit permettre à l'utilisateur de spécifier les éléments suivants :
- le type d'ordonnancement à utiliser ;
- éventuellement le nombre de ressources disponibles ;
- le nombre de processus ;
- pour chaque processus son PID, sa date de création, enventuellement sa priorité et ses événements ;
Les événements d'un processus doivent pouvoir être saisis comme une liste d'opérations. Chaque opération possède une date de départ qui se comprend, non en temps absolu, mais en temps d'exécution du processus. Les opérations peuvent être du type appropriation de ressource, libération de ressource ou arrêt du processus. Pour l'appropriation ou la libération de ressources, l'utilisateur doit pouvoir préciser le numéro de cette ressource.
Une fois tous les éléments précisés, la simulation d'ordonnancement est lancée directement sur le navigateur en JavaScript. La simulation se termine si tous les processus s'arrêtent ou si un interblocage se produit. Le chronogramme est alors affiché, il est demandé de soigner cet affichage.
L'autre aspect du projet consiste à étudier les différentes variantes des algorithmes d'ordonnancement. En effet, dans votre cours de systèmes d'exploitation, les algorithmes ne sont pas totalement spécifiés en particulier concernant la gestion des ressources. Programmez ces différentes variantes et affichez les chronogrammes de toutes les variantes.
Pour commencer vous pouvez vous baser sur le programme C et le script shell de cette archive Fichier:OrdonChrono.zip. Le script shell assure la création du graphique à l'aide de gnuplot.
Cahier des charges
Planning prévisionnel
Travail effectué
Formulaire et stockage des données
Pour commencer, je me suis orienté vers la partie 1 de mon projet c'est-à-dire l'écriture de l'interface utilisateur pour décrire les processus à ordonnancer. J'ai commencé à travailler à l'aide de notepad++ pour la partie en HTML. Dans ce premier fichier HTML, je demandais à l'utilisateur de sélectionner son type d'ordonnancement (FIFO, Tourniquet, Priorité avec préemption, Priorité avec âge et quantum de temps), de choisir son nombre de ressources et son nombre de processus. Pour cela, j'ai choisi une balise de type "select" permettant après à l'utilisateur de choisir son ordonnancement. Ensuite pour les ressources et les processus j'ai choisi de mettre des input de type nombre pour choisir un nombre. Enfin j'ai créé un bouton "envoyer" qui permet à l'utilisateur d'envoyer son formulaire.
Après cela j'ai voulu récupérer les données du formulaire que j'avais crée en HTML. J'ai donc créer un nouveau fichier ".php" pour récupérer ces différentes données. Mais après avoir installé Wampserveur, je n'arrivais pas à récupérer les données du formulaire. J'ai alors décidé de passer sous une machine virtuelle linux où j'ai installé Apache2 et php5. Une fois cela réalisé, j'ai réussi à récupérer les données de mon formulaire. J'ai donc réalisé le code "php" suivant pour récupérer les différentes données et les afficher :
<?php
if(isset($_POST['submit'])){
$ordonnancement = $_POST['ordonnancement'];
$ressources = $_POST['ressources'];
$name_1 = $_POST['processus'];
echo "$ordonnancement\n";
echo "$ressources\n";
echo "$processus\n";
}
Dans notre condition if, nous mettons la condition "isset($_POST['submit'])" pour qu'une fois que l'utilisateur envoie le formulaire nous récupérons les différentes valeurs d'ordonnancement, ressources et processus.
Une fois cela réalisé, je voulais rendre ma page un peu plus dynamique pour les différents ajouts de processus c'est pourquoi j'ai commencé à rechercher des fonctions en Javascript pour pouvoir réaliser ce que je désirais. J'avais alors le code suivant qui me permettait d'ajouter les 4 champs que je voulais pour le processus c'est-à-dire son PID, sa date de création, sa priorité et ses événements :
function create_champ(i) {
var i2 = i + 1;
document.getElementById('leschamps_'+i).innerHTML = 'Processus :
<input type="input" name="name_'+i+'">PID
<input type="input"
name="name_'+i+'">Date de creation
<input type="input" name="name_'+i+'">Priorite
<input type="input" name="name_'+i+'">Evenements
</span>';
document.getElementById('leschamps_'+i).innerHTML += (i <=100 ) ? '
<a href="javascript:create_champ('+i2+')">Ajouter un
processus</a>' : ;
}
J'ai donc utilisé "document.getElementById('leschanmps_'+i)" pour renvoyer l'élément dont l'ID est celui spécifié. De plus, il faut ajouter que id est une chaîne représentant l'identifiant de l'élément voulu. Puis, le "innerHTML récupère ou définit tout le balisage et le contenu au sein d'un élément donné. Voici deux captures d'écrans qui permettent de voir l'ajout d'un processus après l'appui sur "ajouter un processus" :
|
|
| Figure 3.1 : Capture d'écran avant d'appuyer sur le bouton | Figure 3.2 : Résultat de cet appui |
Une fois cette première version du formulaire terminée, j'ai commencé à penser aux différentes façons d'imprimer un chronogramme qui récupère mes différentes données. J'ai donc trouvé l'outil WaveDrom permettant de dessiner mes différents chronogrammes. Sachant que j'arrive à récupérer ces différentes données, il fallait que je code les différents algorithme en "php" pour pouvoir dessiner mes différents chronogrammes. J'ai donc dans un premier temps coder l'ordonnancement du tourniquet pour pouvoir l'afficher grâce à WaveDrom, il fallait d'abord définir dans le fichier "php" les lignes suivantes pour pouvoir utiliser cet outil.
<script src="http://wavedrom.com/skins/default.js" type="text/javascript"></script> <script src="http://wavedrom.com/wavedrom.min.js" type="text/javascript"></script>
Par la suite, j'ai obtenu le chronogramme suivant pour le tourniquet avec 4 processus :
J'avais déjà commencé un fichier en "css" pour améliorer la mise en forme de mon application web, ainsi je vais donner un exemple de code pour la bannière où nous verrons le titre :
#banniere{
border: 5px ridge YellowGreen;
text-align:center;
background-color: white;
}
Une fois que nous mettons du texte dans une "
L'outil Canvas
Une fois que j'avais réalisé cela, j'ai relu le cahier des charges car je me demandais s'il n'y avait pas une meilleure solution à mon problème. Et j'ai pu voir que je pouvais utiliser le JavaScript au lieu d'utiliser du PHP. Ainsi, j'ai décidé de reprendre cette partie pour le graphe et de repenser d'une autre manière. J'ai donc commencé par faire de nombreuses recherches pour savoir comment j'allais modéliser mon chronogramme. Après avoir terminé mes nombreuses recherches, j'ai opté pour utiliser l'outil "canvas" qui me permettait de créer une zone de dessin en hauteur et en largeur que nous définissons dans un code html. Ainsi j'ai utilisé le Jvascript pour les chronogrammes de mes différents types d'ordonnancement. Tout d'abord, j'ai défini ma zone de dessin telle que la ligne de code suivante dans mon fichier "html" :
<canvas id="canvas" width="1265" height="385"></canvas>
Ensuite dans un fichier en JavaScript, j'ai ma fonction me permettant de quadriller mon rectangle en choisissant mes différents espacements. De plus, j'ai géré la largeur de mes lignes. J'ai aussi numéroté mes différentes lignes et colonnes pour mieux me repérer. De plus, j'ai décidé de numéroter directement les différents processus sur le côté de mon quadrillage. J'ai aussi choisi les différentes couleurs grâce aux différentes fonctions déjà existantes. Nous pouvons observer cette fonction dans les lignes suivantes :
function drawCanvas() {
var ctx = document.getElementById("canvas").getContext("2d");
ctx.fillStyle = 'rgba(0,37.5,150,37.5)';
ctx.fillRect(0, 0, 1265, 384);
ctx.fillStyle = 'rgb(255,51,0)';
var np = document.forms.form1.nbreProcessus.value;
ctx.lineWidth = 0.3;
ctx.font = '15px new roman';
for (var i = 50, j = 0; i < 1255; i += 30, j++) {
ctx.moveTo(i, 50);
ctx.lineTo(i, 373);
}
for (var i = 50, j = 0; i < 1265; i += 30, j++) {
if (j - 1 % 10 == 0)
ctx.fillText(j, i - 2, 50);
else
ctx.fillText(j, i - 7, 50);
}
ctx.font = '12px new roman';
for (var i = 50, j = 0; i < 377; i += 17, j++) {
if (j < np)
ctx.fillText("P " + j, 20, i + 13);
ctx.moveTo(50, i);
ctx.lineTo(1255, i);
}
ctx.stroke();
}
En effet, cette fonction réalise les différentes choses dites précédemment. J'avais aussi décidé de changer l'aspect de mon formulaire, pour le rendre un peu plus simple. Ainsi, une fois que nous choisissons le nombre de processus, il suffit de rentrer dans les différentes cases telles que "Date de création" ou "Durée du processus" ou encore "Priorité" des chiffres espacés par des virgules. Il me semble judicieux d'ajouter que j'ai désormais un bouton pour "Ordonnancer", celui-ci génère le chronogramme voulu. J'ai un bouton "reset" qui remet à zéro les cases "Date de création", "Durée du processus", "Priorité" et "Nombre de processus". Et j'ai aussi un bouton "Effacer permettant d'effacer le chronogramme. Ainsi si nous voulons 2 processus il suffit d'entrer deux chiffres séparés d'une virgule, (au préalable ne pas oublier de choisir son processus) puis il faut appuyer sur le bouton "Ordonnancer".
Les ordonnancements
Ensuite, j'avais commencé à codé l'ordonnancement de type FIFO. Celui-ci ayant pour but commencer et de terminer des processus dans leur ordre d'arrivée. Ainsi j'ai crée une classe processus, et j'ai codé cet algorithme en reprenant ce principe. De plus, j'ai aussi pris en compte les différents espacements pour former x cases pour une durée x cases données par l'utilisateur. Voici une partie du programme qui permet de réaliser le tracé du processus :
function Process() {
this.nbre;
this.duree = 0;
this.creation = 0;
}
var incx = 0, y = 50;
var x = Number(creationArr[0]) * 30 + 50;
for (var i = 0; i < Number(nbreProcessus * 2 - 1); i++) {
ctx.fillStyle = 'rgba(189,131,155,0.9)';
ctx.fillRect(x + incx, y + 17 * fifo[i].nbre, fifo[i].duree * 30, 17);
incx += fifo[i].duree * 30;
Nous pouvons voir dans la figure 7 un cas simulé à l'aide de mon algorithme de l'ordonnancement FIFO. Comme nous pouvons le voir, c'est bien le premier arrivé qui est terminé en premier.
Après avoir terminé cet algorithme, je me suis lancé sur l'ordonnancement de type Tourniquet ou Round Robin. L'ordonnancement de type Tourniquet a pour but de partager son temps d'utilisation avec les différents processus. Ainsi, une fois que le quantum est choisi par l'utilisateur nous avons le tourniquet qui commence à se mettre en place. J'ai donc décidé de donner le choix du quantum à l'utilisateur, une fois l'ordonnancement terminé, l'utilisateur peut en ré-appuyant sur "Ordonnancer" changer son quantum et refaire une simulation avec les mêmes données de bases. Dans la fonction du Round Robin, je demande à l'utilisateur d'entrer un quantum, puis je donnais le quantum demandés au processus tout en enlevant à la durée totale du processus ce quantum :
if (ready.count() > 0) {
dequed = true;
dequedP = ready.deq();
if (dequedP.duree > quantumT) {
bPrint = Number(quantumT);
dequedP.duree -= Number(quantumT);
ran += Number(bPrint + 1);
var temp = new Process();
temp.nbre = dequedP.nbre;
temp.duree = bPrint;
temp.creation = dequedP.creation;
processQue.enq(temp);
}
else {
bPrint = dequedP.duree;
dequedP.duree = Number(0);
ran += Number(bPrint + 1);
var temp = new Process();
temp.nbre = dequedP.nbre;
temp.duree = Number(bPrint);
temp.creation = Number(dequedP.creation);
processQue.enq(temp);
}
Ensuite comme précédemment j'ai géré les différents tracés des processus. De plus, j'ai changé la couleur du chronogramme car la couleur bleue n'était pas en adéquation avec les autres couleurs de mon application web. Ci-dessous, nous pouvons voir un exemple de scénario d'ordonnancement avec la figure 8.1 où nous pouvons voir que l'utilisateur entre le quantum désiré. Puis dans la figure 8.2 nous voyons le tracé du chronogramme.
|
|
| Figure 8.1 : Choix du quantum par l'utilisateur | Figure 8.2 : Tracé du Round Robin |
Une fois ce type d'ordonnancement terminé, je me suis lancé sur l'ordonnancement avec priorité. Je me suis lancé dans un premier temps sur un ordonnancement sans préemption. Et celui-ci fonctionne, j'avais repris le même principe que l'ordonnancement FIFO. Comme nous pouvons le voir dans la capture ci-dessous, nous avons bien une gestion des priorités mais nous n'avons pas de préemption. J'avais une petite erreur concernant la préemption, de ce chronogramme c'est pourquoi je l'ai enlevé.
Concernant l'ordonnancement priorité avec âge et quantum de temps, j'avais commencé à penser à l'algorithme mais je n'ai pas pu le réaliser. Le principe de cet ordonnancement étant qu'à chaque tranche de temps, la priorité des tâches éligibles voient leur priorité augmenter. De plus, à priorité égale c'est la plus ancienne éligible qui est élue. Il faut aussi ajouter qu'une tâche suspendu retrouve sa priorité initiale.
Conclusion
Pour conclure, lors de ce projet j'ai réalisé une interface pour mon application web. Cette application web avait pour but de simuler différents ordonnancements. Après avoir fait de nombreuses recherches j'ai utilisé de nouveaux outils tels que canvas ou WeveDrom, mes deux premiers ordonnancements fonctionnent alors que l'ordonnancement avec la priorité + préemption n'est pas terminé. J'espère que le travail réalisé correspond à vos attentes.
