Discussion :

[mina_mi]

bonsoir,
j'ai un problème pour résoudre un exo qui consiste à gérer l'ordonnancement des processuspar la politique FIFO avec préhemption
la 1ère question c'est dessiner le graphe d'ordonnancement de ces processus
les donné sont sous forme de tableau constitué de:
"ordre d'arrivé" (de t1 jusqu'à t7)
"la durée" (700,400,600,100,200,400,100)
et "Date d'arrivé" (0,0,100,100,150,200,200)
le temps de commutation est de 10ms et le quantum est de 100ms
ma question c'est comment programmer ceci avec java , C/C++ , delphi ou un simple algorithme et j'aimerais bien soivoir aussi a quoi ça sert "Date arrivée".
je vous prie de bien vouloir m'aider

[TheGzD]

"Date d'arrivée" est ton événement perturbateur. Si tu pouvais réaliser à T=0 toutes les tâches, il te serait possible de déterminer un ordonnancement qui ne serait pas pertuber par la suite => aucune préemption.

A ce propos comment marche ton système de préemption : retiens tu le temps de traitement déjà réalisé ou pas ?

Pour réaliser ton ordonnancement quels sont les critères que tu utilises ? en clair quelle politique d'ordonnancement utilises-tu ?

Autre question par laquelle j'aurais peut-être du commencer : as-tu un algorithme à ta disposition ?

Dernière question : as-tu clairement compris ce qu'est "le graphe d'ordonnancement des processus" ?

Voila Répond moi et je pense pouvoir être en mesure de t'aider ^^

[mina_mi]

merci pour votre réponse ,

alors pour vos questions:
1.oui je retiens le temps de traitement déja réalisé

2.j'utilise la politique FIFO avec préemption et sans priorité, c à d le processus T1 commence du 0 il reste un temps de 100 ms puis il cède la place à T2 et ainsi de suite avec un temps de commutation de 10 ms jusqu'à ce que la durée de tout les processus arrive à sa fin

3.je ne dispose pas d'un algorithme

4.et je n'ai pas trop bien compris c'est quoi un graphe d'ordonnancement , je crois que ça sert à planifier l'ordonnancement des tache.

je vous remercie encors

[TheGzD]

Ok tes questions m'ont bien éclaircis

Tu as donc affaire à une sorte de scheduler : tu peux le voir sous la forme d'une file d'attente à un seul serveur qui traite ses clients en 110ms (100 de traitement et 10 de changement). Cette file est gérée avec une politique FIFO et tu réinjectes un client que tu as traité dedans (après qu'il soit passé dans le serveur) si son temps total de traitement n'est pas entièrement réalisé. Sommes-nous d'accord jusque là ?

Je présume que ce que tu veux obtenir c'est l'odre de fin de traitement des activités, je me trompe ? On ne parle pas d'ordonnancement normalement, car ce terme représente normalement un ordre d'entrée (à determiner d'ailleurs, alors que je ne vois pas ce qu'il y a à déterminer dans ton problème vu qu'on a déjà les dates d'arrivée oO). Pour ce qui est du terme "préemption" il est un peu mal employé, car la vraie préemption ce n'est pas ça : on s'agit normalement d'une interruption du traitement en cours par le serveur, car il doit traiter un client de plus haute priorité que celui qu'il était en train de traiter. L'événement déclencheur pourrait par exemple être l'entrée d'un client dans la file, alors qu'ici un entrée n'a pas d'influence sur le traitement d'un serveur. Je ne te jette pas la pierre rassure toi, mais je voulais juste éclaircir ces quelques points de détails ^^


*Dit moi ce que tu penses de cet algorithme de principe :

float temps = 0; /* horloge de ta simulation */

string[] processus = {t1, t2, t3, t4, t5, t6, t7} /* là j'ai fait 3 listes mais je te conseille plutot d'implémenter une seule liste qui contiendra des objets contenant les triplets de valeurs dont on a besoin}
float[] temps_processus = {700, 400, 600, 100, 200, 400, 100}
float[] arrivée_processus = {0, 0, 100, 100, 150, 200, 200}
(string, float)[] sortie_processus = {} /* variable de résultat */

file échéancier = init_file(); /* tu peuples la file avec les éléments dont le traitement commence à min(arrivée_processus) et qui les retire de "processus" (n'oublies pas non plus d'assigner ce min à "temps" )*/

Tant que processus!=ensemble_vide faire /* en doit traiter tout les processus */
| Tant que échéancier!=ensemble_vide faire /* on doit traiter tous les processus contenus par la file*/
| | Traiter(file.first());
| fait;
| Arrivée_processus(temps, min(arrivée_processus[])); /* si la file est vide mais qu'il te reste des processus, tu en trouve dans la liste des arrivées (au moins un) à traiter puis tu les insére dans la file */
| temps = min(arrivée_processus[]);
fait;



*Voici le détail de la fonction Traiter :
Traiter(string process)
| int i = process.position(); /* récupére la postion i dans "processus" de process (ça ne sera pas nécessaire si tu utilises la structure dont je t'ai parlé plus haut) */
| temps_processus(i) -= 100;
| float last_temps = temps; /* on retient le temps en début de traitement */
| temps += 110; /* on met à jour l'horloge */
| Si temps_processus(i) == 0 alors
| Arrivée_processus(last_temps, temps); /* tu fais entrer dans la file tous les éléments dont le temps d'arrivée est compris entre "last_temps" et "temps" (attention l'odre d'arrivée n'est pas forcément l'ordre dans lequel tu vas déterminer les éléments qui doivent rentrer!) (à toi de l'implémenter je ne vais pas tout te faire ) */
| | sortie_processus[] += (processus[i], temps); /* on ajoute nom et le temps du processus totalement traité au résultat */
| | processus[] -= processus[i]; /* on retire l'élément traité au 3 ensembles */
| | temps_processus[] -= temps_processus[i];
| | arrivée_processus[] -= arrivée_processus[i];
| | file.defile(); /* tu enlève l'élément de tête */
| Sinon file.enfile(file.defile()); /* tu met lélément de tête en fin de la file */
| finsi;
fin;


Bon je te met en garde : j'ai fait tout ça très rapidement donc il y a surement des fautes ou des cas auxquels je n'ai pas pensé ^^. Tout n'est pas implémenté, de plus il s'agit d'un algo de principe qu'il te faudra porter dans le langage de ton choix. J'espère que tu comprendras ce que j'ai voulu faire et que ça t'aidera

Pour ton graphe poses toi les question suivantes:
- que doivent représenter les noeuds ?
- que doivent représenter les arcs ?


Bon courage pour la suite

[mina_mi]

je vous remercie infinément pour vos réponses et aussi d'avoir éclairci certains points .
je vais travailler sur votre algorithme
et si j'ai des petites questions à vous poser directement est ce que je peux t'envoyer un mp?

[TheGzD]

De rien je l'ai fait avec plaisir

Si tu as des questions n'hésite pas à me les poser : si tu veux me les poser en pm y a pas de problème, mais tu peux aussi simplement me les poser ici même pour que ça puisse servir à certaines personnes qui pourraient se poser le mêmes questions que toi