Is there a theory in the study of priority queues that states that as a job gets closer to completion it should become of higher priority?

Basically at work I see all of this low priority work that seems to never get completely done because of its low priority status. My theory with this is that as the low priority stuff gets closer to completion that it should get a higher priority to get it out of the queue.

I am sure this has to have been addresses in CS field.

__________________
http://www.whatisorganicliving.com
http://www.againstthemainstream.com/

"Banned by BAUT" Alumni (2008)

From a CS point of view...No. CS is more geared toward time sharing without respect of longevity. If a job has a priority, then it means it will most likely get the resources it needs as it becomes available, and the priority systems make sure that lower priority jobs still get some slice of what's going on. (or not locked completely away).

So; equating it with your example (which I also see a lot at work), the idea would be to set aside time for low priority jobs. As long as there is some time available, then the job will progress at the same pace that it did all along. That is as long as the workload is steady.

__________________
Numbers are not case sensitive. (me)

This becomes a problem when low priority items are still a priority ... and even though at all times high priority items are a higher priority I think the difference in the prioritorization factors are set to large.

The age of a job ( how long since it was started ) and the closeness to completion should be taken into account at least in the workplace for low priority tasks.

__________________
http://www.whatisorganicliving.com
http://www.againstthemainstream.com/

"Banned by BAUT" Alumni (2008)

boggleThat can be addressed without affecting the "how long since it was started issue"Why? Doesn't a lower priority essentially mean that there is less need for that particular job to exit the queue? Less need than other (higher priority) jobs, right?

The priority scheme itself might allocate resources, and notice that a job was close to finishing (how?), and decide that it would be more efficient to let it finish rather than spend time to swap. But that should already be built in, if it's possible.

I agree, but I've never heard of any theories to support it. And, this is more of a perception, planning and people issue than it is of a logic or system issue.
Throw some money on the table, and then watch what happens to priorities.
I've also seen lingering projects because the most difficult decisions keep getting delayed. At the end of the project, those are still there, as does final acceptance which won't happen until that project is complete. I don't see much in the way of a theory that can address that either.

__________________
Numbers are not case sensitive. (me)

CS = computer sciences?

Right; in other words, if you want to finish the job, then don't assign a new one with a higher priority. Logically; that is doing the exact opposite of the intended result.
In CS, this is accomplished through queue, resource, and job limits (quotas). There's no way for a higher priority job to even hit the system if a resource has reached it's quota.

__________________
Numbers are not case sensitive. (me)

Yes; For some of us, the context was automatic...sorry.

__________________
Numbers are not case sensitive. (me)

One way to do it is to periodically re-evaluate priorities--if the low-priority job is still low priority (by the same criteria used originially--which MIGHT take into consideration cost, to include time left to complete the job), it stays such, otherwise not. In general, if low-cost meant higher priority (i.e. more bang for buck), which is often the case, then as a task nears completion, its priority would in fact go up. I think the best strategy to achieve this is to have well-defined criteria for prioritization, that takes into account both cost and benefit to finish it given what has already been done, and periodically apply it to all tasks.

__________________
-----
Todd (Bowie, MD, US, North America, Earth, Sol System, Vega region, Local Bubble, Orion arm, Milky Way Galaxy, Local Group, Virgo A Cluster, Virgo supercluster, the universe in which spock is clean shaven)

Quidquid latine dictum sit, altum sonatur.

personal page: http://blog.astrosketches.info

If I remember my OS classes at all, I think "the UNIX way" was to queue up a job lot (not the whole job, but a standard unit of processing time) based on its original priority, and every few cycles, jobs still on the queue get their priority bumped up one level. Keeps low priority jobs from starving, but high priority jobs still get a higher proportion of processing time.

In CS the preemptive scheduler can't tell how much of the job is remaining, so it's not a factor in deciding who gets processor time.

__________________
[Dr. Horrible]___________________________[Penny]
Listen close to everybody's heart________And you believe there's good in everybody's heart
And hear that breaking sound_____________Keep it safe and sound
Hopes and dreams are shattering apart____With hope you can do your part
And crashing to the ground_______________To turn a life around

Yes; I can't remember the Unix words, but in the VMS world that was quanta (they're all pretty much the same, so the language might not be different exept for marketing purposes). If a job gets a quanta, it drops back down to it's base priority. Every pass of checking priorities will bump up any of those that haven't recieved thier quanta.

__________________
Numbers are not case sensitive. (me)

I'm pretty sure quanta wasn't the word I'd heard in class. If I remember in a reasonable time-frame, I'll let you know.

__________________
[Dr. Horrible]___________________________[Penny]
Listen close to everybody's heart________And you believe there's good in everybody's heart
And hear that breaking sound_____________Keep it safe and sound
Hopes and dreams are shattering apart____With hope you can do your part
And crashing to the ground_______________To turn a life around

However in the real world the low priority stuff is still supposed to get done while new high priority stuff gets added to the queue continuously.
There is a need to balance it. I guess not the same a computer program.

you get a lot of: "we need this but not tomorrow" but eventually they will ask you for status.

__________________
http://www.whatisorganicliving.com
http://www.againstthemainstream.com/

"Banned by BAUT" Alumni (2008)

I like this. In fact much of the "do this when you can" stuff ... has to do with optimizations of the system. they have a way to do something but there is a better way ... not real important but can save time.

__________________
http://www.whatisorganicliving.com
http://www.againstthemainstream.com/

"Banned by BAUT" Alumni (2008)

Right, and in the computer world... that's when servers crash.

__________________
Numbers are not case sensitive. (me)

clock cycle?

__________________
http://www.whatisorganicliving.com
http://www.againstthemainstream.com/

"Banned by BAUT" Alumni (2008)

if its windows.

__________________
http://www.whatisorganicliving.com
http://www.againstthemainstream.com/

"Banned by BAUT" Alumni (2008)

Nope. Clock cycle is to quanta (still haven't remembered the word) what atom is to brick.

__________________
[Dr. Horrible]___________________________[Penny]
Listen close to everybody's heart________And you believe there's good in everybody's heart
And hear that breaking sound_____________Keep it safe and sound
Hopes and dreams are shattering apart____With hope you can do your part
And crashing to the ground_______________To turn a life around

Time slice?

__________________
"It's over you head now. Time to get some professional help." - My fortune cookie from lunch

Ned Wright's Cosmology Tutorial

Usenet Physics FAQ