Programmer un ordonnanceur

bonsoir,
j'ai un problème pour résoudre un exo :cry: 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

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

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 :roll: , je crois que ça sert à planifier l'ordonnancement des tache.

je vous remercie encors

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

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

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 ;)

salut TheGzD
je voudrais savoir comment calculer le temps d'attente et le temps de rendement (qui est définit comme étant le rapport du temps pendant lequel l'UC exécute les processus/temps total de traitement)?

j'ai vu des exo comment calculer le temps de réponse et le temps de service, est ce que ça y a une relation?

et si tu as des liens intéréssant pour ce genre d'éxo et ces corrigés tu peux me les envoyé

désolé de t'avoir tant dérangé et encors merci

Ah te voilà arriver dans la phase d'évaluation des performances ^^

Comment définis tu ton "temps d'attente" ? Si tu ne m'en dis pas plus ça peut vouloir dire beaucoup de choses ;)

Pour calculer le "temps de rendement" (très mauvais terme d'ailleurs, car tu le définit comme étant un taux et non un temps (tu vois de quoi je parle là ? :) )) :
1) on va commencer par le nommer "taux d'activité" ça sonnera moins faux :D
2) il te faut déterminer le temps total de la simulation : pour cela il faut apporter une petite correction à l'algo que je t'ai proposé. Il faut remplacer "temps = min(arrivée_processus[]);" par "temps = max(temps,min(arrivée_processus[]));" pour qu'en fin des 2 Tant que tu puisses récupérer la valeur dans "temps" (c'est d'ailleurs à cet endroit que tu devras effectuer tous tes calculs d'indicateurs de performances).
J'aimerai vraiment que tu essayes de comprendre cela histoire que je ne te prémache pas tout ;)
3) il te faut maintenant déterminer le temps total d'activité de ton serveur : si tu as compris mon code il te suffit de rajouter une petite variable au bon endroit dont tu mettras la valeur à jour au bon moment ^^
4) finalement il ne te reste qu'à faire ton ratio à l'endroit que je t'ai indiqué en 2) ;)

Désolé je n'ai pas de liens à te proposer ni même d'exo, mais je reste à ta dispo pour répondre à tes question. Par contre il serait bien que tu commence à me montrer concraitement ce que tu as fais, car je ne vais pas faire ton tp à 100% :mouarf: .
Le plus important et surtout que tu comprennes ce que tu fais, sinon tu ne sauras pas adapter ce raisonnement à d'autres cituations.

rassure toi je ne vais pas te demandé de faire mon TP à ma place ;) parce que l'algorithme est une question suplémentaire, la question de notre TD c'est juste dessiner le graphe (avec un crayon et une feuille :lol: ) et calculer le tps d'attente et le taux d'activité, mais je le fait pour le prochain TP :arf: (je rigole) en réalité un algorithme m'aide à mieu comprendre le problème en question (mais si notre prochain TP portera sur c'est tant mieux )