priority_queue with dynamic priorities
- by Layne
Hey,
I have a server application which accepts incomming queries and executes them. If there are too many queries they should be queued and if some of the other queries got executed the queued queries should be executed as well. Since I want to pass queries with different priorities I think using a priority_queue would be the best choice.
e.g. The amout of the axcepting queries (a) hit the limt and new queries will be stored in the queue. All queries have a priority of 1 (lowest) if some of the queries from (a) get executed the programm will pick the query with the highest priority out of the queue and execute it. Still no problem. Now someone is sending a query with a priority of 5 which gets added to the queue. Since this is the query with the highest priority the application will execute this query as soon as the running queries no longer hit the limit. There might be the worst case that 500 queries with a priority of 1 are queued but wont be executed since someone is always sending queries with a priority of 5 hence these 500 queries will be queued for a looooong time. In order to prevent that I want to increase the prioritiy of all queries which have a lower priority than the query with the higher priority, in this example which have a priority lower than 5. So if the query with a priority of 5 gets pulled out of the queue all other queries with a priority < 5 should be increased by 0.2. This way queries with a low priority wont be queued for ever even if there might be 100 queries with a higher priority.
I really hope can help me to solve the problem with the priorities:
Since my queries consist of an object I thought something like this might work:
class Query {
public:
Query( std::string p_stQuery ) : stQuery( p_stQuery ) {};
std::string getQuery() const {return stQuery;};
void increasePriority( const float fIncrease ) {fPriority += fIncrease;};
friend bool operator < ( const Query& PriorityFirst, const Query& PriorityNext ) {
if( PriorityFirst.fPriority < PriorityNext.fPriority ) {
if( PriorityFirst.fStartPriority < PriorityNext.fStartPriority ) {
Query qTemp = PriorityFirst;
qTemp.increasePriority( INCREASE_RATE );
}
return true;
} else {
return false;
}
};
private:
static const float INCREASE_RATE = 0.2;
float fPriority; // current priority
float fStartPriority; // initialised priority
std::string stQuery;
};
