IMA4 2017/2018 P68 : Différence entre versions

De Wiki de Projets IMA
(Algorithmes d'ordonnancements)
(Documents rendus)
 
(19 révisions intermédiaires par le même utilisateur non affichées)
Ligne 26 : Ligne 26 :
 
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.
 
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.
  
=Préparation du projet=
+
=Partie interface WEB=
 +
 
 +
=== <u>Formulaire et stockage des données avant la reprise dès la phase initiale du projet</u>===
 +
 
 +
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.
 +
 
 +
[[Fichier:ecrtiure_interface.jpg|500px|thumb|center|Figure 1 : Écriture de l'interface]]
 +
 
 +
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.
 +
 
 +
[[Fichier:recup_donnees.jpg|500px|thumb|center|Figure 2 : Récupération des données du formulaire HTML]]
  
==Cahier des charges==
+
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 : 
==Choix techniques : matériel et logiciel==
 
==Liste des tâches à effectuer==
 
(Écrire les tâches réalisées et les restantes)
 
  
==Calendrier prévisionnel==
+
function create_champ(i) {
 +
 
 +
var i2 = i + 1;
 +
 +
document.getElementById('leschamps_'+i).innerHTML = 'Processus : <br/><input type="input" name="name_'+i+'">PID<br/><input type="input"
 +
name="name_'+i+'">Date de creation<br/><input type="input" name="name_'+i+'">Priorite<br/><input type="input" name="name_'+i+'">Evenements<br/></span>';
 +
document.getElementById('leschamps_'+i).innerHTML += (i <=100 ) ? '<br /><span id="leschamps_'+i2+'"><a href="javascript:create_champ('+i2+')">Ajouter un
 +
processus</a></span>' : '';
 +
 
 +
}
  
=Réalisation du Projet=
+
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" :
==Feuille d'heures==
 
  
{| class="wikitable"
+
{| style="float: center; height: 160px; margin-left:0.2em; border: 1px solid #bbb;"
!Tâche !! Prélude !! Heures S1 !! Heures S2 !! Heures S3 !! Heures S4 !! Heures S5 !! Heures S6 !! Heures S7 !! Heures S8 !! Heures S9 !! Heures S10 !! Total
+
| style="border: 1px solid #bbb;" valign="top" |[[File:ajout_avant.JPG|500px]]
|-
+
| style="border: 1px solid #bbb;" valign="top" |[[File:ajout_apres.JPG|500px]]
| Analyse du projet
+
|- style="font-size: 87%; text-align: center;"
| 0
+
| valign="center" | Figure 3.1 : Capture d'écran avant d'appuyer sur le bouton
|  
+
| valign="center" | 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.
 +
 +
<!-- Wavedrom pour le tracé des chronogrammes -->
 +
<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 :
 +
 +
[[Fichier:wavedrom.jpg|500px|thumb|center|Figure 4 : Tracé de chronogrammes avec WaveDrom]]
 +
 +
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 un <code>div</code>, nous aurons le texte qui sera encadré par une bordure d'une largeur de 5px ayant pour couleur le jaune/vert. De plus, le texte sera tout le temps centré et la couleur d'arrière plan sera blanche. J'ai créer d'autres mises en formes de la sorte pour mon application web, telle que le corps qui est encadré par une bordure bleue. Nous pouvons voir cela dans la capture d'écran suivante :
 +
 +
[[Fichier:mise_en_forme.jpg|600px|thumb|center|Figure 5 : Mise en forme de l'application web]]
 +
 +
 +
 +
===<u> Prise de recul pour changer le formulaire et le rendre dynamique </u>===
 +
 +
Pour commencer, cette interface graphique doit être de type WEB. L'objectif de cette partie est de récupérer les différentes données entrées par l'utilisateur. Ainsi, il faut que l'utilisateur puisse choisir son type d'ordonnancement, le nombre de ressources disponibles, le nombre de processus. De plus, pour chaque processus son PID, sa date de création, sa priorité et ses événements.
 +
 +
Au départ, j'ai voulu réaliser un formulaire où il fallait choisir le type d'ordonnancement. Ensuite, il fallait choisir le nombre de processus allant de 1 à 5. Une fois choisi, nous avions toutes les éléments que nous voulions.
 +
 +
[[Fichier:formulaire_v2.jpg|600px|thumb|center|Figure 6 : Affichage d'une des premières versions du formulaire]]
 +
 +
'''Points à améliorer :'''
 +
 +
*Pouvoir choisir un nombre de processus
 +
*Ne pas avoir que 6 événements, mais pouvoir les entrer et que cela soit dynamiquement
 +
*Le nombre de sémaphores qui est de 3
 +
*Changement de méthode pour que le formulaire soit totalement dynamiquement
 +
 +
 +
 +
Dans ce projet, il y a différents fichiers un fichier contenant les algorithmes « chrono.js », la partie gérant la partie affichage à l'aide de la bibliothèque chart.js qui est « affichage.js ». Ensuite, il y a le fichier « formulaire.html » qui contient le formulaire.
 +
 +
Au début, j'avais pensé à utiliser le PHP pour récupérer les différentes données du formulaire mais cela ne répondait plus au cahier des charges. Il fallait utiliser le JavaScript.
 +
 +
Pour répondre à ces différents besoins, il était nécessaire de rendre dynamique le formulaire. Dans un premier temps, il a donc fallu créer un premier fichier « interface.html » qui est l'interface permettant d'introduire les différents processus à ordonner. Dans un second temps, il a fallu créer un fichier « script.js » qui permet de rendre le formulaire dynamique.
 +
 +
 +
 +
Lorsque nous accédons à l'interface principale nous constatons le présence de 4 éléments :
 +
 +
*Un groupe de boutons radio facilitant le choix de l'algorithme
 +
*Un champ « input » permettant de choisir le nombre de processus
 +
*Un second champ « input » permettant cette fois-ci de choisir le nombre de ressources
 +
*Et enfin un bouton « valider », pour valider les différentes informations entrées par l'utilisateur.
 +
 +
 +
 +
Dans le fichier "interface.html", nous avons donc une première partie du formulaire. Dans cette première partie, nous demandons à l'utilisateur de sélectionner le type d'ordonnancement, le nombre de processus et le nombre de ressources. Une fois toutes ces données entrées, l'utilisateur valide son choix. Une fois ce choix effectué, j'avais eu l'idée de masquer les données précédentes. Sachant que je voulais que le code soit dynamique, j'ai donc décidé de créer un fichier "script.js" me permettant de gérer la partie dynamique du formulaire.
 +
 +
 +
 +
Dans mon fichier HTML, j'ai créée une classe "hide" comme cela :
 +
 +
<div class="hide" class="form-inline">
 +
 +
Et comme je l'ai expliqué précédemment, je voulais cacher la première partie du formulaire une fois que celle-ci était rentrée et validée. C'est donc ainsi que j'ai utilisé du jQuery.
 +
 +
 +
 +
<u>Qu'est-ce que le jQuery ?</u>
 +
 +
« Jquery est une bibliothèque JavaScript libre et multiplateforme créée pour faciliter l'écriture de scripts côté client dans le code HTML des pages web. » (Définition wikipédia)
 +
 +
 +
 +
Sachant que je voulais cacher la première partie du formulaire une fois que l'utilisateur, j'ai donc effectué quelques recherches et j'ai trouvé qu'il existait une fonction permettant de réaliser cela. Après avoir caché cette partie du formulaire, il ne fallait pas oublier d'enregistrer le nombre de processus, le nombre de ressources et le choix du type d'ordonnancement. Nous pouvons observer cela dans la partie de code du fichier "script.js" qui suit :
 +
 +
$("#valider").on("click", function(e) {
 +
    $(".hide").hide();
 +
    nbre_proc = parseInt($(".nbreproc").val());
 +
    nbre_res = parseInt($(".nbreres").val());
 +
    radio = $("fieldset input[type='radio']:checked").val();
 +
   
 +
Après avoir validé les différents éléments choisis, nous sommes mené vers une interface des processus. Ensuite, le nombre de processus choisi est récupéré par une fonction jquery, celle-ci ajoute le nombre de champs nécessaires.
 +
 +
Dans cette interface des processus, nous avons le nombre de processus que nous avons choisi. Ainsi, pour chaque processus nous avons :
 +
 +
*Un champ pour le PID
 +
*Un champ pour la date de création
 +
*Un champ pour la priorité
 +
*Un champ « input » permettant d'entrer le nombre d'événements. J'ai donc ajouté un bouton permettant la validation de ce nombre choisi. Une fois le click enclenché nous avons le nombre d'événements qui s'affiche.
 +
*Ces événements sont composés d'un temps, d'un type d'opérations et du choix d'une ressource
 +
 +
 +
Une fois tous les champs remplis par l'utilisateur, nous devons cliquer sur le bouton « envoyer ». Après avoir cliqué nous récupérons toutes les données qui permettent le bon fonctionnement des différents algorithmes d'ordonnancement.
  
  
==Prologue==
 
=Partie interface WEB=
 
=Algorithmes d'ordonnancements=
 
  
Explication des différentes variantes d'ordonnancement que j'ai choisi pour le moment.
+
'''<u>Difficultés rencontrées :</u>'''
 +
 
 +
Dans cette partie, j'ai rencontré plusieurs problèmes tels que pour dynamiser le formulaire par un script JavaScript, il faut savoir manipuler correctement le « DOM » du fichier HTML. Le DOM permet à des scripts d’examiner et de modifier le contenu du navigateur web. Ce fut donc compliqué car il est plus simple de gérer des éléments statiques que de gérer des éléments ajoutés dynamiquement.
 +
 
 +
De  plus, j'ai eu quelques difficultés pour gérer les événements dans la partie de l'interface processus.
  
 
=Gestion de l'affichage=
 
=Gestion de l'affichage=
  
Dans cette partie je vais expliquer mon choix d'affichage, puis je vais devoir montrer que celui-ci ne fonctionne pas que statiquement mais dynamiquement.
+
Concernant la partie affichage j'ai d'abord pensé à utiliser WaveDrom. Mais cela était assez limité, pour pouvoir bien tracer les différents processus. J'ai donc cherché différentes solutions pour pouvoir avoir un affichage correcte. J'avais donc les options suivantes :
 +
 
 +
*PlotKit
 +
*JS Charts
 +
*Flot
 +
 
 +
J'ai préféré utiliser la librairie Charts.js qui était très bien documentée, avec de nombreux exemples.  De plus j'ai donc tracé les chronogrammes, le résultat était assez esthétique. Il y a l'affichage des légendes, du chronogramme et des instants de capture des ressources ainsi que leur relâchement.
 +
 
 +
J'ai donc pris un certain temps pour la prise en main de cette bibliothèque, j'ai d'abord commencé par réaliser quelques exemples et étudier des exemples déjà existants. Cette étape fut essentielle pour que je comprenne comment il fallait introduire la légende, mais aussi pour pouvoir choisir l'aspect de visualisation pour le type d'opération, j'ai choisi différentes formes permettant de visualiser cela.
 +
 
 +
[[Fichier:exemple_affichage.jpg|600px|thumb|center|Figure 7 : Affichage d'un exemple qui m'a amené à penser à l'affichage final]]
 +
 
 +
Comme dit précédemment, on n'affichait seulement 5 processus au départ. Sachant que nous avons dynamisé l'interface, il faut aussi rendre l'affichage dynamique. C'est-à-dire qu'il faut que les légendes s'affichent dynamiquement. Et que le cadrage et l'utilisation des différents espaces sur le graphique se fassent automatiquement.
 +
 
 +
Une fois ces parties modifiées concernant l'affichage, j'ai réalisé quelques tests. Ainsi, j'ai pensé à randomiser les couleurs pour ne pas avoir le problème d'avoir les mêmes couleurs pour des processus différents.
 +
 
 +
 
 +
'''<u>Problèmes rencontrés :</u>'''
 +
 
 +
*Lorsque que j'avais un processus qui avait un PID supérieur à 5 celui-ci ne s'affichait pas, il a donc fallu augmenter l'axe des ordonnées du graphique tout en prenant en compte le nombre de processus.
 +
*Sachant que le PID d'un processus ne commence pas toujours par 1, il a fallu ajouter un attribut indice au constructeurs des processus qui prenait le numéro des différents processus.
 +
 
 +
 
 +
 
 +
Ensuite, j'ai réalisé quelques tests qui m'ont permis de voir que les données des processus reçues depuis le formulaire ne sont pas ordonnées par leur date de création. De plus, les événements ne sont pas ordonnées par leur temps. Il a donc fallu réaliser un triage de données pour assurer le bon fonctionnement des différents algorithmes.
 +
Pour finir ces tests, j'ai entré des données à l'aide du formulaire. Mais j'ai pu remarquer que les données du formulaire arrivent vides. J'ai donc recherché des solutions et j'ai trouvé celles-ci :
 +
 
 +
*Utilisation du PHP
 +
*Utiliser mes 4 fichiers HTML qui fonctionnaient statiquement mais qui ont été modifié. Et les mettre dans un fichier JavaScript « fonction.js »
 +
 
 +
Comme je l'avais expliqué précédemment, le PHP ne répond pas au cahier des charges. J'ai donc choisi la seconde solution.
 +
 
 +
=Partie ordonnancement et variante=
 +
 
 +
Les différents choix des types d'ordonnancements sont :
 +
 
 +
*<u>FIFO :</u> FIFO signifie First In, First Out. Cet ordonnancement fonctionne de la manière suivante premier entré, premier sorti.
 +
 
 +
*<u>Tourniquet :</u> Le tourniquet fonctionne de la manière suivante, chaque processus se voit attribuer un intervalle de temps appélé « quantum » pendant lequel il est autorisé à s'exécuter. Une fois son « quantum » terminé, celui-ci s'arrête pour laisser le tour à un autre processus. Et s'il lui reste encore du temps, ce processus repart en queue de liste pour attendre son prochain tour.
 +
 
 +
*<u>Priorité avec préemption :</u> Ce type d'ordonnancement fonctionne de la manière suivante, chaque processus détient un niveau de priorité, et si le processus qui arrive dans la file d'attente est plus prioritaire que celui en cours d'exécution il y aura alors réquisition du processeur en faveur du processus arrivant.
 +
 
 +
*<u>Priorité avec âge et quantum de temps :</u> Le principe de cet ordonnancement est le suivant, les processus sont élus en fonction de leur priorité. A chaque fin de « quantum », les processus en attente ont leur priorité qui se voit augmentée. Et une fois que l'un d'entre eux a une priorité plus élevé que le processus en cours alors il prend sa place d’exécution. Et une fois son « quantum » terminé, il reprend sa priorité initiale.
 +
 
 +
 
 +
 
 +
J'ai ensuite réalisé une phase de recherche concernant la gestion des ressources, dans mon cas les processus peuvent demander autant de ressources souhaitées. Nous avons alors parfois des interblocages car les processus obtiennent des accès exclusifs aux différentes ressources. Nous sommes donc en interblocage si chaque processus attend la libération d’une ressource qui est allouée à un autre processus de l’ensemble. Comme tous les processus sont en attente, aucun ne pourra s’exécuter et donc libérer les ressources demandées par les autres. Ils attendront tous indéfiniment.
 +
 
 +
 
 +
 
 +
J'ai donc commencé à étudier différents algorithmes me permettant de mieux comprendre le problème de la gestion des ressources :
 +
 
 +
*<u>Le dîner des philosophes :</u> Nous avons par exemple 5 philosophes qui se retrouvent autour d'un table, chacun a une assiette devant lui et à gauche de chaque assiette il y a une fourchette. Chaque philosophe a trois états « penser », « être affamé » et « manger ». Lorsqu'un des philosophes a faim, il se met en état « affamé » et attend que les fourchettes soient libres car il doit utiliser la fourchette à sa droite et celle à sa gauche. Et si au moins une des fourchettes n'est pas libres alors il reste en état « affamé » avant de pouvoir retenter sa chance après un temps déterminé. Le problème a donc pour but de trouver un ordonnancement pour que ces philosophes puissent manger chacun leur tour.
 +
 
 +
*<u>La politique de l'autruche :</u> cela consiste à éviter le problème en disant qu'il n'y a pas d'interblocage.
 +
 
 +
*<u>L'algorithme du banquier :</u> Cet algorithme est un algorithme d’évitement des interblocages qui s’applique dans le cas général où chaque type de ressources possède plusieurs instances. Lorsqu'un nouveau processus entre dans le système, il doit déclarer les ressources dont il aura besoin. Un processus n'a pas le droit d'utiliser toutes les ressources existantes. Lors de son exécution, quand un processus demande un ensemble de ressources, il y a ensuite une vérification pour s'assurer que le système ne sera pas grandement affecté.
 +
 
 +
 
 +
Après différentes recherches j'ai choisi de réaliser une variante ne permettant pas à un processus de demander plusieurs ressources à la fois. Et il a fallu regarder si chaque ressources demandées étaient bien relâchées par chaque processus. Si ce n'était pas le cas j'ai décidé de les relâcher systématiquement un peu avant la fin de leur temps d'exécution.
 +
 
 +
=Démonstration=
 +
 
 +
Dans cette partie, je vais réaliser une démonstration en mettant quelques captures d'écrans de mon application Web. Je vais choisir le scénario suivant :
 +
 
 +
*Nous choisissons 3 processus
 +
*Nous choisissons 10 ressources (même si nous ne les utilisons pas toutes lors de cette exemple)
 +
*Puis nous choisissons par exemple l'ordonnancement de type FIFO
 +
*Ensuite nous validons notre choix
 +
 
 +
[[Fichier:formulaire_partie1.jpg|600px|thumb|center|Figure 8 : Affichage de la première partie du formulaire]]
 +
 
 +
Nous pouvons donc observer qu'il n'y a plus la première partie du formulaire comme expliqué précédemment. Une fois cela terminé, nous entrons les données suivantes :
 +
 
 +
Pour le premier processus :
 +
 
 +
*PID = 1
 +
*Date de création = 5
 +
*Priorité = 20
 +
*Événements → Demande R1 à 10, Relâche R1 à 20 et on stoppe à 25. Ici on demande alors 3 événements. 
 +
 
 +
 
 +
Ensuite pour le second processus :
 +
 
 +
*PID = 2
 +
*Date de création = 0
 +
*Priorité = 30
 +
*Événements → Demande R2 à 5, Relâche R2 à 25 et on stoppe à 50. Dans ce cas nous demandons aussi 3 événements. 
 +
 
 +
 
 +
Et pour le dernier processus nous entrons cela :
 +
 
 +
*PID = 3
 +
*Date de création = 10
 +
*Priorité = 1
 +
*Événements → Demande R4 à 10, Relâche R1 à 25, Demande R6 à 35, Relâche R6 à 55,  et on stoppe à 100. On demande alors 5 événements.
 +
 
 +
Voici une visualisation de la seconde partie du formulaire.
 +
 
 +
[[Fichier:formulaire_partie2.jpg|600px|thumb|center|Figure 9 : Affichage de la seconde partie du formulaire]]
 +
 
 +
Une fois toutes ces données entrées, nous validons et obtenons la capture d'écran suivante :
 +
 
 +
[[Fichier:affichage_chronogramme.jpg|600px|thumb|center|Figure 10 : Affichage de l'ordonnancement une fois le formulaire envoyé]]
 +
 
 +
Comme nous pouvons le voir, il y a une légende et par exemple chaque processus possède sa couleur, et chaque ressource à aussi sa propre couleur. De plus, nous pouvons observer que la simulation fonctionne correctement car c'est bien le deuxième processus qui commence, puis le premier et enfin le dernier. Et si nous regardons les différentes dates de création nous pouvons observer que cela est valide.
 +
 
 +
J'ai ensuite réalisé un test en utilisant la seconde option permettant un gestion des ressources différentes. Ainsi, j'avais décidé de ne jamais relâcher des ressources et elles ont été relâché automatiquement un peu avant la fin de son temps.
 +
 
 +
[[Fichier:pas_de_release_chronogramme.jpg|600px|thumb|center|Figure 10 : Affichage de l'ordonnancement sans relâchement]]
 +
 
 +
=Conclusion=
 +
 
 +
Pour finir, ce projet a donc abouti à une application Web exploitable, mais perfectible. J'ai pu développer des compétences techniques. Les difficultés que j'ai rencontré sont avant tout techniques puisqu'il m'a fallu apprendre de nouveaux langages de programmation : JavaScript et CSS. Je tiens donc à ajouter qu'une grosse partie de mon travail a donc consisté à réaliser une phase de recherche d'informations concernant ces langages, mais aussi concernant la gestion des ressources.
 +
 
 +
=Documents rendus=
 +
 
 +
[[Fichier:rapportP68_2018.pdf]]
 +
 
 +
[[Média:P68_Samy_Belhouachi.zip]]
  
 
=Documents Rendus=
 
=Documents Rendus=

Version actuelle datée du 19 mai 2018 à 21:12


Présentation générale

Description

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, éventuellement 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.

Objectifs

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.

Partie interface WEB

Formulaire et stockage des données avant la reprise dès la phase initiale du projet

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.

Figure 1 : Écriture de l'interface

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.

Figure 2 : Récupération des données du formulaire HTML

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" :

Ajout avant.JPG Ajout apres.JPG
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 :

Figure 4 : Tracé de chronogrammes avec WaveDrom

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 un div, nous aurons le texte qui sera encadré par une bordure d'une largeur de 5px ayant pour couleur le jaune/vert. De plus, le texte sera tout le temps centré et la couleur d'arrière plan sera blanche. J'ai créer d'autres mises en formes de la sorte pour mon application web, telle que le corps qui est encadré par une bordure bleue. Nous pouvons voir cela dans la capture d'écran suivante :

Figure 5 : Mise en forme de l'application web


Prise de recul pour changer le formulaire et le rendre dynamique

Pour commencer, cette interface graphique doit être de type WEB. L'objectif de cette partie est de récupérer les différentes données entrées par l'utilisateur. Ainsi, il faut que l'utilisateur puisse choisir son type d'ordonnancement, le nombre de ressources disponibles, le nombre de processus. De plus, pour chaque processus son PID, sa date de création, sa priorité et ses événements.

Au départ, j'ai voulu réaliser un formulaire où il fallait choisir le type d'ordonnancement. Ensuite, il fallait choisir le nombre de processus allant de 1 à 5. Une fois choisi, nous avions toutes les éléments que nous voulions.

Figure 6 : Affichage d'une des premières versions du formulaire

Points à améliorer :

  • Pouvoir choisir un nombre de processus
  • Ne pas avoir que 6 événements, mais pouvoir les entrer et que cela soit dynamiquement
  • Le nombre de sémaphores qui est de 3
  • Changement de méthode pour que le formulaire soit totalement dynamiquement


Dans ce projet, il y a différents fichiers un fichier contenant les algorithmes « chrono.js », la partie gérant la partie affichage à l'aide de la bibliothèque chart.js qui est « affichage.js ». Ensuite, il y a le fichier « formulaire.html » qui contient le formulaire.

Au début, j'avais pensé à utiliser le PHP pour récupérer les différentes données du formulaire mais cela ne répondait plus au cahier des charges. Il fallait utiliser le JavaScript.

Pour répondre à ces différents besoins, il était nécessaire de rendre dynamique le formulaire. Dans un premier temps, il a donc fallu créer un premier fichier « interface.html » qui est l'interface permettant d'introduire les différents processus à ordonner. Dans un second temps, il a fallu créer un fichier « script.js » qui permet de rendre le formulaire dynamique.


Lorsque nous accédons à l'interface principale nous constatons le présence de 4 éléments :

  • Un groupe de boutons radio facilitant le choix de l'algorithme
  • Un champ « input » permettant de choisir le nombre de processus
  • Un second champ « input » permettant cette fois-ci de choisir le nombre de ressources
  • Et enfin un bouton « valider », pour valider les différentes informations entrées par l'utilisateur.


Dans le fichier "interface.html", nous avons donc une première partie du formulaire. Dans cette première partie, nous demandons à l'utilisateur de sélectionner le type d'ordonnancement, le nombre de processus et le nombre de ressources. Une fois toutes ces données entrées, l'utilisateur valide son choix. Une fois ce choix effectué, j'avais eu l'idée de masquer les données précédentes. Sachant que je voulais que le code soit dynamique, j'ai donc décidé de créer un fichier "script.js" me permettant de gérer la partie dynamique du formulaire.


Dans mon fichier HTML, j'ai créée une classe "hide" comme cela :

Et comme je l'ai expliqué précédemment, je voulais cacher la première partie du formulaire une fois que celle-ci était rentrée et validée. C'est donc ainsi que j'ai utilisé du jQuery.


Qu'est-ce que le jQuery ?

« Jquery est une bibliothèque JavaScript libre et multiplateforme créée pour faciliter l'écriture de scripts côté client dans le code HTML des pages web. » (Définition wikipédia)


Sachant que je voulais cacher la première partie du formulaire une fois que l'utilisateur, j'ai donc effectué quelques recherches et j'ai trouvé qu'il existait une fonction permettant de réaliser cela. Après avoir caché cette partie du formulaire, il ne fallait pas oublier d'enregistrer le nombre de processus, le nombre de ressources et le choix du type d'ordonnancement. Nous pouvons observer cela dans la partie de code du fichier "script.js" qui suit :

$("#valider").on("click", function(e) {
    $(".hide").hide();
    nbre_proc = parseInt($(".nbreproc").val());
    nbre_res = parseInt($(".nbreres").val());
    radio = $("fieldset input[type='radio']:checked").val();
   

Après avoir validé les différents éléments choisis, nous sommes mené vers une interface des processus. Ensuite, le nombre de processus choisi est récupéré par une fonction jquery, celle-ci ajoute le nombre de champs nécessaires.

Dans cette interface des processus, nous avons le nombre de processus que nous avons choisi. Ainsi, pour chaque processus nous avons :

  • Un champ pour le PID
  • Un champ pour la date de création
  • Un champ pour la priorité
  • Un champ « input » permettant d'entrer le nombre d'événements. J'ai donc ajouté un bouton permettant la validation de ce nombre choisi. Une fois le click enclenché nous avons le nombre d'événements qui s'affiche.
  • Ces événements sont composés d'un temps, d'un type d'opérations et du choix d'une ressource


Une fois tous les champs remplis par l'utilisateur, nous devons cliquer sur le bouton « envoyer ». Après avoir cliqué nous récupérons toutes les données qui permettent le bon fonctionnement des différents algorithmes d'ordonnancement.


Difficultés rencontrées :

Dans cette partie, j'ai rencontré plusieurs problèmes tels que pour dynamiser le formulaire par un script JavaScript, il faut savoir manipuler correctement le « DOM » du fichier HTML. Le DOM permet à des scripts d’examiner et de modifier le contenu du navigateur web. Ce fut donc compliqué car il est plus simple de gérer des éléments statiques que de gérer des éléments ajoutés dynamiquement.

De plus, j'ai eu quelques difficultés pour gérer les événements dans la partie de l'interface processus.

Gestion de l'affichage

Concernant la partie affichage j'ai d'abord pensé à utiliser WaveDrom. Mais cela était assez limité, pour pouvoir bien tracer les différents processus. J'ai donc cherché différentes solutions pour pouvoir avoir un affichage correcte. J'avais donc les options suivantes :

  • PlotKit
  • JS Charts
  • Flot

J'ai préféré utiliser la librairie Charts.js qui était très bien documentée, avec de nombreux exemples. De plus j'ai donc tracé les chronogrammes, le résultat était assez esthétique. Il y a l'affichage des légendes, du chronogramme et des instants de capture des ressources ainsi que leur relâchement.

J'ai donc pris un certain temps pour la prise en main de cette bibliothèque, j'ai d'abord commencé par réaliser quelques exemples et étudier des exemples déjà existants. Cette étape fut essentielle pour que je comprenne comment il fallait introduire la légende, mais aussi pour pouvoir choisir l'aspect de visualisation pour le type d'opération, j'ai choisi différentes formes permettant de visualiser cela.

Figure 7 : Affichage d'un exemple qui m'a amené à penser à l'affichage final

Comme dit précédemment, on n'affichait seulement 5 processus au départ. Sachant que nous avons dynamisé l'interface, il faut aussi rendre l'affichage dynamique. C'est-à-dire qu'il faut que les légendes s'affichent dynamiquement. Et que le cadrage et l'utilisation des différents espaces sur le graphique se fassent automatiquement.

Une fois ces parties modifiées concernant l'affichage, j'ai réalisé quelques tests. Ainsi, j'ai pensé à randomiser les couleurs pour ne pas avoir le problème d'avoir les mêmes couleurs pour des processus différents.


Problèmes rencontrés :

  • Lorsque que j'avais un processus qui avait un PID supérieur à 5 celui-ci ne s'affichait pas, il a donc fallu augmenter l'axe des ordonnées du graphique tout en prenant en compte le nombre de processus.
  • Sachant que le PID d'un processus ne commence pas toujours par 1, il a fallu ajouter un attribut indice au constructeurs des processus qui prenait le numéro des différents processus.


Ensuite, j'ai réalisé quelques tests qui m'ont permis de voir que les données des processus reçues depuis le formulaire ne sont pas ordonnées par leur date de création. De plus, les événements ne sont pas ordonnées par leur temps. Il a donc fallu réaliser un triage de données pour assurer le bon fonctionnement des différents algorithmes. Pour finir ces tests, j'ai entré des données à l'aide du formulaire. Mais j'ai pu remarquer que les données du formulaire arrivent vides. J'ai donc recherché des solutions et j'ai trouvé celles-ci :

  • Utilisation du PHP
  • Utiliser mes 4 fichiers HTML qui fonctionnaient statiquement mais qui ont été modifié. Et les mettre dans un fichier JavaScript « fonction.js »

Comme je l'avais expliqué précédemment, le PHP ne répond pas au cahier des charges. J'ai donc choisi la seconde solution.

Partie ordonnancement et variante

Les différents choix des types d'ordonnancements sont :

  • FIFO : FIFO signifie First In, First Out. Cet ordonnancement fonctionne de la manière suivante premier entré, premier sorti.
  • Tourniquet : Le tourniquet fonctionne de la manière suivante, chaque processus se voit attribuer un intervalle de temps appélé « quantum » pendant lequel il est autorisé à s'exécuter. Une fois son « quantum » terminé, celui-ci s'arrête pour laisser le tour à un autre processus. Et s'il lui reste encore du temps, ce processus repart en queue de liste pour attendre son prochain tour.
  • Priorité avec préemption : Ce type d'ordonnancement fonctionne de la manière suivante, chaque processus détient un niveau de priorité, et si le processus qui arrive dans la file d'attente est plus prioritaire que celui en cours d'exécution il y aura alors réquisition du processeur en faveur du processus arrivant.
  • Priorité avec âge et quantum de temps : Le principe de cet ordonnancement est le suivant, les processus sont élus en fonction de leur priorité. A chaque fin de « quantum », les processus en attente ont leur priorité qui se voit augmentée. Et une fois que l'un d'entre eux a une priorité plus élevé que le processus en cours alors il prend sa place d’exécution. Et une fois son « quantum » terminé, il reprend sa priorité initiale.


J'ai ensuite réalisé une phase de recherche concernant la gestion des ressources, dans mon cas les processus peuvent demander autant de ressources souhaitées. Nous avons alors parfois des interblocages car les processus obtiennent des accès exclusifs aux différentes ressources. Nous sommes donc en interblocage si chaque processus attend la libération d’une ressource qui est allouée à un autre processus de l’ensemble. Comme tous les processus sont en attente, aucun ne pourra s’exécuter et donc libérer les ressources demandées par les autres. Ils attendront tous indéfiniment.


J'ai donc commencé à étudier différents algorithmes me permettant de mieux comprendre le problème de la gestion des ressources :

  • Le dîner des philosophes : Nous avons par exemple 5 philosophes qui se retrouvent autour d'un table, chacun a une assiette devant lui et à gauche de chaque assiette il y a une fourchette. Chaque philosophe a trois états « penser », « être affamé » et « manger ». Lorsqu'un des philosophes a faim, il se met en état « affamé » et attend que les fourchettes soient libres car il doit utiliser la fourchette à sa droite et celle à sa gauche. Et si au moins une des fourchettes n'est pas libres alors il reste en état « affamé » avant de pouvoir retenter sa chance après un temps déterminé. Le problème a donc pour but de trouver un ordonnancement pour que ces philosophes puissent manger chacun leur tour.
  • La politique de l'autruche : cela consiste à éviter le problème en disant qu'il n'y a pas d'interblocage.
  • L'algorithme du banquier : Cet algorithme est un algorithme d’évitement des interblocages qui s’applique dans le cas général où chaque type de ressources possède plusieurs instances. Lorsqu'un nouveau processus entre dans le système, il doit déclarer les ressources dont il aura besoin. Un processus n'a pas le droit d'utiliser toutes les ressources existantes. Lors de son exécution, quand un processus demande un ensemble de ressources, il y a ensuite une vérification pour s'assurer que le système ne sera pas grandement affecté.


Après différentes recherches j'ai choisi de réaliser une variante ne permettant pas à un processus de demander plusieurs ressources à la fois. Et il a fallu regarder si chaque ressources demandées étaient bien relâchées par chaque processus. Si ce n'était pas le cas j'ai décidé de les relâcher systématiquement un peu avant la fin de leur temps d'exécution.

Démonstration

Dans cette partie, je vais réaliser une démonstration en mettant quelques captures d'écrans de mon application Web. Je vais choisir le scénario suivant :

  • Nous choisissons 3 processus
  • Nous choisissons 10 ressources (même si nous ne les utilisons pas toutes lors de cette exemple)
  • Puis nous choisissons par exemple l'ordonnancement de type FIFO
  • Ensuite nous validons notre choix
Figure 8 : Affichage de la première partie du formulaire

Nous pouvons donc observer qu'il n'y a plus la première partie du formulaire comme expliqué précédemment. Une fois cela terminé, nous entrons les données suivantes :

Pour le premier processus :

  • PID = 1
  • Date de création = 5
  • Priorité = 20
  • Événements → Demande R1 à 10, Relâche R1 à 20 et on stoppe à 25. Ici on demande alors 3 événements.


Ensuite pour le second processus :

  • PID = 2
  • Date de création = 0
  • Priorité = 30
  • Événements → Demande R2 à 5, Relâche R2 à 25 et on stoppe à 50. Dans ce cas nous demandons aussi 3 événements.


Et pour le dernier processus nous entrons cela :

  • PID = 3
  • Date de création = 10
  • Priorité = 1
  • Événements → Demande R4 à 10, Relâche R1 à 25, Demande R6 à 35, Relâche R6 à 55, et on stoppe à 100. On demande alors 5 événements.

Voici une visualisation de la seconde partie du formulaire.

Figure 9 : Affichage de la seconde partie du formulaire

Une fois toutes ces données entrées, nous validons et obtenons la capture d'écran suivante :

Figure 10 : Affichage de l'ordonnancement une fois le formulaire envoyé

Comme nous pouvons le voir, il y a une légende et par exemple chaque processus possède sa couleur, et chaque ressource à aussi sa propre couleur. De plus, nous pouvons observer que la simulation fonctionne correctement car c'est bien le deuxième processus qui commence, puis le premier et enfin le dernier. Et si nous regardons les différentes dates de création nous pouvons observer que cela est valide.

J'ai ensuite réalisé un test en utilisant la seconde option permettant un gestion des ressources différentes. Ainsi, j'avais décidé de ne jamais relâcher des ressources et elles ont été relâché automatiquement un peu avant la fin de son temps.

Figure 10 : Affichage de l'ordonnancement sans relâchement

Conclusion

Pour finir, ce projet a donc abouti à une application Web exploitable, mais perfectible. J'ai pu développer des compétences techniques. Les difficultés que j'ai rencontré sont avant tout techniques puisqu'il m'a fallu apprendre de nouveaux langages de programmation : JavaScript et CSS. Je tiens donc à ajouter qu'une grosse partie de mon travail a donc consisté à réaliser une phase de recherche d'informations concernant ces langages, mais aussi concernant la gestion des ressources.

Documents rendus

Fichier:RapportP68 2018.pdf

Média:P68_Samy_Belhouachi.zip

=Documents Rendus=