Re: Random weighted selection...

Seamus MacRae wrote:
Pat wrote:
So I need a way to have my jobs in a queue (effectively, not
necessarily literally) where they are waiting for this function to
pull them off for completion. I've done a lot of searching for this in
any language, and can't find anything as short and elegant as the
routine I remember from so many years ago.

Has anyone ever heard of/seen something liek this in theory or
practice?

One way to do it is: when a new job is to begin, sum the job priorities, generate a random number uniformly distributed between 0 and one less than that sum, then iterate over the jobs again totting up their priorities until the total exceeds the random number, then execute the last job visited in the iteration.

Note: the above requires the job priorities to be positive. Zero or negative priority jobs will accumulate to the head of the list and never get run.

This does not give more recent jobs priority over less.

Or vice-versa. Which in your case is apparently more desirable.

A simple variant has a single express line that accepts the highest priority job currently on the queue for its next job

perhaps breaking a tie by picking the least recently added of the jobs tied for highest priority

and a normal line that accepts the frontmost job on the queue,
regardless of its priority; this one works well for CPU-bound tasks on
dual-core machines when you want high-priority jobs done ASAP but every
job guaranteed to run eventually.

This by the way has the interesting property that no job will be kept waiting to execute longer than with a simple FIFO queue on a single-CPU machine of the same clock speed. Lowest-priority jobs take an average of twice as long to get run than with a simple FIFO queue on the dual-core machine, while highest-priority jobs run as soon as the current job being run by the "express consumer" is done. They can be made to run immediately with added sophistication: for each job priority (possible or actual) but the lowest there is a thread of proportional priority that consumes jobs of that priority from the queue and has affinity for one core; one more thread consumes jobs from the queue's head regardless of priority and has affinity for the other core. No job of priority N waits for a job of priority N-1 or less; if no other job of priority N or more is queued or running, it runs immediately on the "high priority core" and pre-empts other jobs. The downside here is once a job is started by one of the priority-based threads, it can get starved by an influx of higher-priority jobs. Further sophistication might allow a job starved for long enough to be moved to the other core, or rolled back and reinserted into the queue to have a chance to be run by that core (or when the glut of high-priority jobs has passed, if that happens soon enough).

If the thread scheduler is sophisticated enough, one might just have a thread for each priority, with no affinity, but all with the same thread priority on one core and with increasing priorities on the other. This requires a scheduler that lets threads have per-CPU priorities instead of a global one. The "low priority core" won't run the jobs it runs in strict FIFO order, but timeshare a few at a time, and jobs added sooner will complete sooner and all will complete eventually. Indeed, if all the higher-priority jobs are done and a while passes without any new ones, a job may then even start running on the other core and be done swiftly.

I don't know of such a scheduler, and in a Java application, it would depend on the host OS. One way to fake it would be to implement jobs in a coroutine-style: they are Objects with a doABitMore() method that returns true (or maybe a non-null result object encapsulating one or more return values) when the job's done, and with the property that one invocation of doABitMore() does very little. This adds some overhead (the more the finer the time-slice granularity of the doABitMore() methods) but lets you write your own scheduler. It can have two threads, a job queue, and the threads calling doABitMore() on (respectively) the highest-priority job and the frontmost job. (The job has to be taken out of the queue before doABitMore() is called, and put back in its place after this returns if the job's not done; this is probably best done not by actually remove()ing it but by flagging it in some way, perhaps by setting a volatile boolean.)

Needless to say, the above works well for CPU-bound jobs, but not so well for I/O jobs. (Print jobs especially -- you'll get pages, or worse, PARTS of pages, interleaved!)

If the jobs have well-defined deadlines and estimatable durations, an alternative to simple queueing is to try to schedule the jobs like appointments or TV shows, with some algorithm finding a best fit of the jobs in (possibly one-per-CPU)

or printer, or server in the farm, or other such resource

queues such that they should complete before their deadlines.

One more possible area of sophistication is in favoring shorter jobs (if there's some reasonably reliable estimate of job size -- particularly, it should never think a job will be brief that ends up taking ages; there should be an upper bound on how wrong it will be in proportion to the estimate, e.g. "a job will take no more than 50% longer than estimated"). The estimate itself might best be an upper bound on job duration, if you can manage this.

Short jobs can then be given a priority boost, or an express line of their own. The latter can be especially useful with office printers, where people want to be able to print short things (a page or two) and get them immediately, but sometimes very long reports or sheafs of legalese or the like get enqueued. Having all jobs of over 10 pages, say, routed to a particular printer or printers and all others to other printers avoids a short and urgent job getting stuck behind the equivalent of a slow-moving truck on a highway with no passing lanes.

With job length and priority both factors, you might have four (or more) queues in a two-dimensional space based on those factors, or use job length as a weight that modulates job priority. (Time the job has already been waiting was already noted as another possible weight to modulate job priority, earlier.)
.

Quantcast