• Post Reply Bookmark Topic Watch Topic
  • New Topic

from a round robin algorithm to best-fit  RSS feed

 
tina Kmaal
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,
I am trying to develop a mechanism to know which machine can handle a user job (by providing his Requirements) for now I wrote this method but it is a Round robin, I am trying to modify it to a best-fit algorithm can anybody give me tips about how should I begin?

 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello "may qq",
welcome to JavaRanch.

We're a friendly group, but we do require members to have valid display names.

Display names must be two words: your first name, a space, then your last name. Fictitious names are not allowed.

Please edit your profile and correct your display name.
Thanks, and have fun!
 
tina Kmaal
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
sorry I thought that I can put any first and last names
I changed it
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks like this will return the first machine that has enough cpu, disk and memory. What would you like it to return instead?
 
tina Kmaal
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I want it to return the best machine, for exapmle if I have two machines:
M1(cpu:23,mem:512,diskspace:10233),M2(cpu:50,mem:490,desk:2300)
and the user want a machine with desk:500, then I want the second machine to be allocated to the user not the first although the two can handle the job
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
you need to change your method to not quit when it finds the first machine that fits.

instead, it needs to loop through the entire list, and remember the best one so far. each time it finds another machine that meets the requirements, it needs to see if it is a "better" fit than the best so far. If not, do nothing. if so, remember this new one instead. You are only done when there are no more to test against.
 
tina Kmaal
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks for the reply I got what you mean, but the problem is that each machine has three attributes so how can I cpmpare the best based on the three atributes...
I'll try it and I'll come back for the feed back

[ December 30, 2006: Message edited by: tina Kmaal ]
[ December 30, 2006: Message edited by: tina Kmaal ]
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13078
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
IF this was my problem I would be thinking in terms of JavaSpaces / "Grid" technology. See various links on the jini.org page.

The Javaspace solution would "put" a user job into a space, where the job object contained the various requirements. Worker machines would request jobs from the space checking requirements and return finished jobs to the space.

Bill
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a little experience with a workflow engine that tries to match each task to the best person to do the job. It can run in very near real time, for example delivering telephony events. It's sounds quite a lot like what you're doing.

Maybe build a little logic in isolation from the rest of the program to define "best fit". Return a score from 0 (won't work at all) to 100 (best possible fit.) Make something like this say "true" all three times:

Does that go after the right problem? You'll also need to make sure the machine you pick is not busy right now, right?
[ December 30, 2006: Message edited by: Stan James ]
 
tina Kmaal
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
that's exactly what I want...How can I do it?
[ December 30, 2006: Message edited by: tina Kmaal ]
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it will be up to you to define "best fit" and compare two candidates. I suggested an exact match on all three requirements gets 100 and anything that fails any requirement gets 0. You may come up with something else.

Think about starting with 100 points (or 0 or whatever) and adding or removing points for difference from the requirements. How would you like to handle a situation where none of the machines has enough memory but one is close? Would having double the requirement for disk space make up for being short on memory? It's going to be tricky to get this to a single score, for sure.

Is this for fun, for school or for a real grid? For the first two you can make up your own rules about what is good and what is bad. For real life, make a best guess, monitor and tweak over time.
 
Nathan Leniz
Ranch Hand
Posts: 132
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I know I'm new to programming but I've helped a friend with a problem like this, though not with computers.

Populate three lists from the available pool. List 1 by cpu, list 2 by memory, list 3 by diskspace. Then process each list so that the one with the closest value to the user needs "wins". Then do a comparison. Select one defining computer attribute that will determine which makes it the best if there are no matches, otherwise, go with one that is the "winner" of two or more of the lists. If you get more than one exact match, then you can define the ultimate winner by your defining attribute. And if it is a really lengthy population list, select two attributes.

Just an idea.
[ January 01, 2007: Message edited by: Nathan Leniz ]
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!