11/02 What is the best way to implement this? I have a queue where jobs
are submitted for processing, and multiple worker threads
asynchronously pull the front job from the queue to process it.
I also have N (N=3)
priority classes. Normally I would just implement this as N FIFO
queues and that would be fine. But wait, there's more! Some jobs
cannot be processed until other jobs (their dependancies) have been
completed. A job and its dependancy may have different priorities.
Then, certain jobs may require the exclusive use of a resource being
used to process a different job in a different worker thread being
fed from the same pool of jobs (think dining philosophers problem).
Any ideas?
\_ Classic priority inversion problem.
\_ Is this your 162 homework assignment?
\_ Nah, extending an existing system for work. -OP
\_ This sounds amazingly similar to some of the job queueing stuff
handled by Sun's N1 Grid Engine. You might be able to adapt it
to your use, or if not, grab the source -- Sun publishes this --
and see how they solved the same problems. (We use N1GE and
our users are pretty happy with it) -ERic
\_ Grid computing? NOOOOOOOO!!!!
\_ and in spite of the name, it is not really Grid
computing, it is more of a batch job submission /
processing engine. A great way to distribute tasks
across many systems. SUN Marketing FTL -ERicx
across many systems. SUN Marketing FTL -ERic
\_ Here is a link to the source:
http://gridengine.sunsource.net/servlets/ProjectSource
GridEngine is a decent piece of code written by fairly
good engineers. I worked on a interdepartment project
w/ the N1GE team while at Sun and they were very nice
responsive people.
I used to work w/ the N1GE group when I was at Sun, if
you need a contact, I can find out who is currently
working on queue mgmt.
\_ and in spite of the name, it is not really Grid
computing, it is more of a batch job submission /
processing engine. A great way to distribute tasks
across many systems. SUN Marketing FTL -ERic
\_ Would it be an acceptable solution to have multiple threads
processing the jobs that have no dependencies, but have only
one thread process jobs with dependencies? That thread could
then do a topological sort on the elements in its queue when
it goes to read from the queue. I guess after sorting, the
job entire dependency graph could be handed to a worker thread...
- ciyer
\_ There may be a high fraction of jobs with (relatively simple)
dependancy graphs. I'm thinking when a job with dependancies
gets queued, it's dependancies can get (upwards only) priority
inheritance. |