priority queues

[tommac]

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.

[NEOWatcher]

...I am sure this has to have been addresses in CS field.
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.

[tommac]

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.


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.

[hhEb09'1]

This becomes a problem when low priority items are still a priority ... boggleand even though at all times high priority items are a higher priority I think the difference in the prioritorization factors are set to large.That can be addressed without affecting the "how long since it was started issue"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.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.

[NEOWatcher]

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.
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.

[geonuc]

CS = computer sciences?

[NEOWatcher]

That 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?
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.
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.
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.

[NEOWatcher]

CS = computer sciences?
Yes; For some of us, the context was automatic...sorry.

[tdvance]

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.

[Moose]

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.

[NEOWatcher]

If I remember my OS classes at all...
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.

[Moose]

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.

[tommac]

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.
.

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.

[tommac]

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.


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.

[NEOWatcher]

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.
Right, and in the computer world... that's when servers crash.

[tommac]

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.

clock cycle?

[tommac]

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

[Moose]

clock cycle?

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

[CodeSlinger]

Time slice?

[Moose]

According to this (http://www-128.ibm.com/developerworks/linux/library/l-scheduler/) document on the Linux implementation of scheduling, the term is indeed "slice", but I'm pretty sure that wasn't the term I'd heard either. Still, it's a recent source from someone who ought to know what he's talking about, so I'm willing to run with it.

Interestingly, there are a few (http://en.wikipedia.org/wiki/Scheduling_%28computing%29#Common_scheduling_disci plines) (dozen) scheduler algorithms. I'm most familiar with the O(1) Scheduler, but that's apparently dating myself. It got thrown over for the Completely Fair Scheduler at some point.

[Torben]

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.

I think to answer this question you have to state some sort of objective. An objective might be:

"Minimize the number of jobs that take longer than X to complete"

or

"Minimize the average amount of time each job spends waiting"

or something else along those lines. If you have a clearly stated, measurable objective, then it would be possible to evaluate specific tactics (like increasing the priority of a job as it gets closer to completion), and how good they are at meeting the objective. But without some stated objective, I don't see how you can say much about whether a specific tactic is a good idea or not.

Also, any such tactic has to be implementable - is there a way to tell how close a job is to completion?

[Whirlpool]

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

I thought ... Customer Service

:doh:

[Neverfly]

I thought ... Customer Service

:doh:

Customer Service?
What is this Customer Service of which you speak?
I think I've never experienced that...

[neilzero]

My first thought was: What a waste of resources if the task is never completed. Then I learned CS = computer science. Is that every human endevor, as all is related to computers at least vaugly? Is OS operating system or does OS have a broader meaning than Vista or Unix?
Examples might help. Your organization paid about one million checks and other disbursments, last month. Obviously the $10,000 and up checks have higher priority than the under a dollar checks. So we can't loose a million dollars if we never determine if the under one dollar checks were a scam. Worse we can spend a million dollars determining who made the disbursments and should they have made them, so it is good that we only spot check the details on the under $100 checks?
If, on the other hand, these are widgets, which failed an inspection criteria, We need to wholesale them to retesters, or we will soon be renting warehouse space to store widgets that we may never retest or even have a customer for. Neil

[Moose]

Neil, many tasks in CS are modeled using human-real-life metaphors. The thing to remember is that while a computer is very good at repetition (better than we are), there is a certain level of decision-making it simply cannot handle.

In human terms, your scenario is one where there are not enough people for too much work for too little revenue. In computer terms, it's possible to overload a machine so that it is unable to react quickly enough to "stimulus". Those conditions would be roughly equivalent.

Processor scheduling deals with issues similar to my own work situation, where we have far too many projects for the time allotted, so project requests were prioritized, from "entire college network cannot function without" ranging down to "nice to have for the one person who needs it."

The "nice to haves" are in a starvation situation right now, and have been for years, because we simply cannot devote any effort to them while there are mission critical projects remaining. Maybe we'll get to them someday, maybe we won't.

But a processor can't easily make value judgments, except through each process's priority level, and starving processes aren't really acceptable in computing. Hence the scheduling algorithms which try to allocate system resources in a way such that everything gets done, only the high priority stuff gets more attention than the low priority stuff.

[NEOWatcher]

Right, and in the computer world... that's when servers crash.if its windows.
Well; It's not limited to windows, but windows is less tolerant of overloads.

The more stable systems will prevent incomming load through queue limits, process limits, and all sorts of other tuned specifications. But; no matter how finely you tune a system, there is something you will run out of.