Algorithme pour traiter des tâches avec la même priorité

Je résous des problèmes d'exercices à partir d'un livre intitulé Algorithms de Papadimitrou et Vazirani.Algorithme pour traiter des tâches avec la même priorité

Voici la question:

Un serveur a des clients n attendant d'être servi. Le temps de service requis par chaque client est connu à l'avance: c'est ti minutes pour le client i. Ainsi, si, par exemple, les clients sont servis dans l'ordre croissant de i, alors le client it doit attendre Sum (j = 1 à n) tj minutes.

Nous souhaitons minimiser le temps d'attente total. Donner un algorithme efficace pour le même.

Ma tentative:

Je pensais que des deux approches, mais couldnt décider qui est le mieux ou toute autre approche que le mien bat.

Approche 1:

les servir dans la mode Round Robin avec tranche de temps 5. Cependant, quand je dois être plus prudent au moment de décider la tranche de temps. Il ne devrait pas être trop haut ou bas. Donc, j'ai pensé à choisir la tranche de temps comme la moyenne des temps de service.

Approche 2: Supposons emplois sont triés en fonction du temps qu'ils prennent et sont stockés dans un tableau A [1 ... n]

premier service A [1] et A [n] et A [ 2] puis A [n-1] et ainsi de suite.

Je ne peux pas vraiment décider quelle solution sera la plus optimale pour ce problème. Est-ce que j'ai raté quelque chose?

Merci, Chander

Source

2010-10-22 Chander Shivdasani

Imaginez que vous ayez seulement deux tâches, l'une courte et l'autre longue ... calculez le temps d'attente en exécutant l'une ou l'autre en premier ... juste pour démarrer votre "algorithme" –

Puis ajoutez la fonction de découpage et voyez si vous gagnez quelque chose ... –

En supposant que le "temps d'attente" pour un client est temps jusqu'à ce que son travail soit terminé, le timeslicing est toujours pire (sauf si vous avez plusieurs processeurs/noyaux et peut migrer des tâches entre eux). Si le travail A est le dernier à être terminé, le fait de le faire plus tôt retarde l'achèvement d'autres tâches, sans que le travail A soit achevé. Il est donc toujours préférable de ne pas commencer le dernier travail avant d'avoir terminé tous les autres travaux. Par induction, vous ne devriez jamais changer d'emploi à mi-parcours. –

Vous pouvez résoudre ce problème en ajoutant la partie tri et improvisant sur votre approche à la ronde,

Trier d'abord les clients en fonction du temps de service

Maintenant, au lieu de simplement donner à chaque client une tranche de temps t de manière à la ronde, vous pouvez également vérifier si le client a moins de t/2 temps restant, le cas échéant remplir sa tâche

Ainsi pour chaque client dans la liste triée du premier client du serveur pour l'instant t si son temps restant est < t/2 puis terminer son service maintenant passer au client suivant

Source

2010-10-22 04:00:03 theReverseFlick

Permettez-moi suppose le « temps d'attente total » est la somme du temps chaque client attend avant l'arrivée du serveur lui servir/elle, et suppose sont servis les clients afin de i de plus en plus , donc client C1 attend t1 minutes, le client C2 attend t1+t2 minutes, et le client C3 attend t1+t2+t3 minutes, et ... client Cn attend t1+t2+...+t{n-1}+tn minutes.

ou:

C1 waits: t1 
C2 waits: t1+t2 
C3 waits: t1+t2+t3 
... 
Cn waits: t1+t2+t3+...tn

Le temps d'attente total fait n*t1+(n-1)*t2+...1*tn

Encore une fois, ceci est basé sur l'hypothèse que les clients sont servis dans l'ordre de plus en plus i.

Maintenant, quel client voulez-vous le serveur en premier?

Source

2010-10-22 01:46:45 YYC

Algorithme pour traiter des tâches avec la même priorité

Répondre

Questions connexes