Homework Help!! Priority Queue ??

[Dani]

Please help me! Some homework help appreciated here, thanks!

I'm trying to simulate a server (e.g. a cpu) which accepts requests (e.g. processes). All requests (theoretically) come in at the same time. Each request consists of the amount of cpu time it needs in addition to a priority on a scale of 1-5 or 1-10 or something to the like. I need a function which calculates a Priority Rating (PR) as well as a "penalty" which manipulates these two variables. My server's queue is then ordered by the PR to decrease the amount of cpu time while still handling priority. In other words, some form of a penalty must be in place the longer high priority processes have to wait in the queue.

Does anyone have any ideas of some general algorithm I can consider? Or somewhere I could go for some help on this. My entire program is written except for this one function:

// THIS IS A DUMMY FUNCTION
// AN APPROPRIATE ALGORITHM WILL BE DETERMINED IN THE FUTURE
int calc_pr(int cpu_time, int request_priority)
{
return (cpu_time * request_priority);
}

[Dani]

If anyone's curious, here's what my lil fake server does as of now ;) My goal is to have a more robust way of queueing processes.

[subtronic]

If anyone's curious, here's what my lil fake server does as of now ;) My goal is to have a more robust way of queueing processes.

Are you allowed to use the Standard Template Library or do you need to implement your own heap with heap sort? Do you know how heap sort works?

[Dani]

Because processes are added to the queue in random places, based on their PR, they're stored via a binary tree. One of my original implementations of this is available at [thread]895[/thread] although it's gone through a few lives since then. (BTW thanks for responding to that thread, too, subtronic).

In any case, my binary queue is sorted based on PR. I've already implemented an inorder traversal function which touches each process from lower PR to higher PR. In addition, I'm currently working on something like a "reheapify" function which can be called at any time, and it "fixes" any inconsistencies in the binary tree should the PR of a process be changed.

Basically what I'm looking for is a nice algorithm to calculate PR given cpu_time, request_priority, and wait_time (how long the server must wait in the queue). In other words, should cpu_time be weighted higher than the priority or vice versa?

[subtronic]

Basically what I'm looking for is a nice algorithm to calculate PR given cpu_time, request_priority, and wait_time (how long the server must wait in the queue). In other words, should cpu_time be weighted higher than the priority or vice versa?

So let's assume PR isn't important right now and let's assume that cpu_time is how things are sorted in the heap, is this a MIN or MAX heap is my first question? Are the jobs that take least time executed first or last? Either way, assuming this is our ownly qualifier, there could be a potential for starvation of a job (this depends, in your case, in which order you add new jobs and complete existing jobs (which a processor would consider an interupt)). This question of which should go first is a really nice question because it really depends on what you're going to do (most processors multiplex using time and will process each job a little at a time). Since I'm assuming you're having to complete a job and then move on to the next, space multiplexing is the only viable option you have. This being the case a nice thing to have is PR. In this case you can specifically set a higher priority which can minimize the likelyhood of starvation or optimally guarantee that a job runs. What I might do to determine priority so that all jobs regardless of cpu_time will fit into the queue and be less likely starved is determine a line of best fit (just off the top of my head).. this will give you the minimal error (which can be used as your priority).. Remember your linear algebra :)? I'm assuming your data will look near linear as you won't have negative times or priorities.

[Dani]

Subtronic, I really do appreciate all your help. I'm going to read your response and get back to you as soon as I can. Just give me a day or two. Unfortunately I came down with a really, really horrible cold and can't even think about programming right now.

[Wiecek5]

Just out of curiousity what class is this ?
As well as do you have to error check? Like for invalid input such as .3 or A.
You want your scheme to go like
Time <-shorter longer-> 1-10
PR <-BEST WORST-> 1-10

A quick easy way is to add the priority with the time length. You will have values ranging from 2 till 20.
2 would be priority of 1 and time of 1. Which i would assume you would want to be first processed. the last item to be processed would be one that has a pr of 10 and a time of 10. You could also make the value of the priority worth more if you want. I can help with that too. Also are you going to constantly be having values come in? if so i think i have a way to deal with that and make sure that

[Wiecek5]

your processes will not starve. sorry bout the second post.