Priority Queues

[kaos]

I'm starting to write a real scheduler in C++. I'm thinking that heaps make the best priority queues, so I decided to make a heap template class. The problem is that references to objects could appear in multiple heaps. I was thinking that the best way around that is to make a type for each kind of priority in the class, something like this:

Code: Select all

template <class Comparable>
class PQueue;

class Thread;

struct ThreadCpuPriorityRef
{
  Thread *p;
};

struct ThreadTimerSignalTimeRef
{
  Thread *p;
};

class Thread
{
  friend bool operator>(ThreadCpuPriorityRef r0, ThreadCpuPriorityRef r1);
  friend bool operator>(ThreadTimerSignalTimeRef r0, ThreadTimerSignalTimeRef r1);
  protected:
    int cpuPriority;
    int threadTimerSignalTime;
    PQueue<ThreadCpuPriorityRef> *cpuPriorityQueue;
    PQueue<ThreadTimerSignalTimeRef> *timerSignalPriorityQueue;
    /* etc */
  public:
    /* etc */
};



template <class Comparable>
class PQueue
{
  protected:
    vector<Comparable> items;
    /* etc */
  public:
    /* etc */
};

PQueue<ThreadCpuPriorityRef> asdf;
PQueue<ThreadTimerSignalTimeRef> bsdf;

Is this the best way to do that? Is there a data structure that makes a better priority queue?

[Tim]

I use an array of sorted linked lists for my scheduler, with one array element for each priority level. I believe Windows NT does the same thing, except that it optimizes it by maintaining a bitmask, with a bit set for each priority level that has at least one thread ready to run.

[Pype.Clicker]

as there are not so much queues (usually barely a dozen of them), i'm unsure a bitmap of non-empty queues will really improve anything ...

A thing i should check is that 'O(1)' scheduler in linux ... If anyone has hints on this ...

[Curufir]

as there are not so much queues (usually barely a dozen of them), i'm unsure a bitmap of non-empty queues will really improve anything ...

A thing i should check is that 'O(1)' scheduler in linux ... If anyone has hints on this ...

Well from what I know it basically runs this way:

There is a FIFO queue of process ids that are ready to run (I'll call it the "runnable" queue), and a FIFO queue of process ids that have been run and aren't blocking (I'll call it the "has run" queue).

The scheduler just takes the top process from the "runnable" queue, runs it and adds it to the bottom of the "has run" queue. Once the "runnable" queue is empty the scheduler switches the queues and continues on. So the whole process is O(1) since there are no searches required.

There's also an awful lot of pre-emptive stuff for user-focussed applications which seriously complicate matters because they can manipulate the scheduler queues in a none FIFO way.

The big point I see is that priority levels indicate relative processor time dedicated to the process, they aren't any indication of how often the process will run. All the time-dependent responsiveness details are handled outside of the part of the scheduler that does task switching. E.g. When you click on a button the button's parent process id is moved into the "runnable" queue as the next process to run.

Note: That's just what I've been able to gather from looking around the net since the O(1) scheduler started being used. I haven't had a chance to see the source ccode yet.

[kaos]

I use an array of sorted linked lists for my scheduler, with one array element for each priority level.

I was thinking about doing the same thing, but I want to have tunable priorities--if a thread makes no syscalls and never blocks unless preempted, its priority should be lowered (or raised, depending on how you do your priorities). If a thread is blocking a lot, its priority should be raised (lowered). I think that there should be bounds on how much the priorities can be adjusted from their base values to ensure that very high priority tasks can always preempt low priority tasks (for realtime processing or whatever). If there are a thousand tasks with a thousand different priorities, having a linked list for each priority won't work. I suppose a hashtable could work, but there are things that I don't like about that idea.

There are well-documented algorithms for increasing/decreasing the priority of objects in a heap. IIRC insertion into a heap is O(1) best case and O(log n) worst case, while deletion from the beginning of a heap is O(log n) all the time.

Round-robin schedulers are generally O(1). They aren't well-suited for interactive or realtime processing though.

[Pype.Clicker]

a hashtable of priority queues doesn't sound like a good idea to me, as there's nothing like an ordering in a hashtable, so you cannot easily know which queue will be the next to be processed once the current queue get empty.

also, i fear there's a misunderstanding on what a 'heap' is, here. Afaik, 'heap' is a memory management term that refers to a pool of memory that can be used to allocate long-living dynamic variables. It has no inherent 'priority' information and algorithms rather do allocation/freeing than insertion/deletion ...

Could you be speaking of a binary tree instead ?

If not, can you provide a link to a page that describes the 'heap' as you plan to use it ...

[kaos]

a hashtable of priority queues doesn't sound like a good idea to me, as there's nothing like an ordering in a hashtable...

Whether or not you one can do ordering in a hashtable depends on the implementation, but you do raise a good point there.

...you cannot easily know which queue will be the next to be processed...

Once again, that depends on the implementation, but I don't think it is a good idea either.

also, i fear there's a misunderstanding on what a 'heap' is, here. Afaik, 'heap' is a memory management term that refers to a pool of memory that can be used to allocate long-living dynamic variables. It has no inherent 'priority' information and algorithms rather do allocation/freeing than insertion/deletion ...

Could you be speaking of a binary tree instead ?

A heap is a kind of binary tree.

If not, can you provide a link to a page that describes the 'heap' as you plan to use it ...

http://csci.biola.edu/csci106/heap.htm

[Pype.Clicker]

Could you be speaking of a binary tree instead ?

A heap is a kind of binary tree.

If not, can you provide a link to a page that describes the 'heap' as you plan to use it ...

http://csci.biola.edu/csci106/heap.htm

oh, okay. So it was a 'heap' such as in 'heap sort' ...

Is there *really* a use for thousands of priority levels ? is it really whishable that your scheduler will enfore so strict ordering between threads ? usually, you want that 'threads that have received datas from I/O get cpu quickly' or that 'threads that must provide data for time-constraint I/O get cpu even quicker' ... But is it really interresting to have to set up priority orders that will tell 'thread A will always get cpu before thread B executes' ?

I'd go for a few dozen of priority classes at max. not for thousands (of course you might have something in mind that require those thousands ;p )

[kaos]

Is there *really* a use for thousands of priority levels ?

The priority level might not be a thread's scheduling priority; it might be a time in a wait queue.

is it really whishable that your scheduler will enfore so strict ordering between threads ?

Yes.

[Pype.Clicker]

Is there *really* a use for thousands of priority levels ?

The priority level might not be a thread's scheduling priority; it might be a time in a wait queue.

Hmm ... something that would, for instance, make A more important than B if A has been waiting for a semaphore for a longer time than B has been waiting for a missing page ?

Or rather something that says 'thread A has been ready without running for so long that it is now more important that anything' ?