How to properly deal with starvation

Question

I'm trying to find a way to avoid starvation in my program, a producer/consumer (two threads, one for each role) problem with four priority levels (four deques).

Basically, the consumer thread always remove from the max priority deque until nothing is left, than it goes to remove to the medium priority deque, and so on.

There may be starvation: what if max priority deque is always full of elements, consumer thread is busy to remove them and low priority elements are never picked up?

I was told to implements some kind of aging mechanism, checking if elements have spent too much time in a deque: if so, take them, reset their timer and push them in a deque with higher priority.

Sounds nice, so I started making a controller thread which could make this task: during the design, some questions arose and I can't find an answer.

How can I proceed to find out the optimal timeout after which the controller thread removes the element and push it in a higher priority deque? How many elements with expired timeout will be removed (one is too little, all the elements may be too much if deque has all elements with timeout expired)?

EDIT: I tried UmNyobe's approach, here's a possible output (each number is the number of elements in that deque; the leftmost number is the max priority deque, the rightmost the low priority deque):

// max prio deque has 3 elements, low prio has 7, others are empty

// first round: remove 4 elements with max prio and one with min prio
3 0 0 7 
2 0 0 7
1 0 0 7
0 0 0 7
0 0 0 6

// second round: remove one element with min prio
0 0 0 5

// third round: remove one element with min prio
0 0 0 4

// fourth round: remove one element with min prio
// and so on...
0 0 0 3

0 0 0 2

0 0 0 1

0 0 0 0

I'm implementing a proxy with priority to connections: e.g., loading a YouTube video will display right away the player (because I gave it max priority, and by removing 4 elements with max prio at once the video is soon showed) but the stylistic elements of the page will take a while to load (because I gave them min priority, and by removing one element with low prio at once, buttons and image previews will take a while to appear).

Maybe I should reverse the order of removal: every X rounds, remove one with max prio and four with low prio, I don't know.

EDIT 2: maybe I should have pointed out that elements stored in deque are requests for connection. So, pending connections for the streaming video have max prio and they will be removed 4 at once from deque; pending connections for the stylistic elements have min prio and they will be removed 1 at once.

What I want to say is that elements stored in deque are not task, thread or other indipendent jobs that will do some stuff: they are what a web page is made of. So, it is fine to give less priority to stylistic elements of web page, but they should be loaded shortly after (immediately?) max prio elements are loaded.

Answer 1

The scheduling mechanism you have described is Fixed-priority pre-emptive scheduling.

If you know there is a possibility the max priority queue is always full, then you are using the wrong mechanism, because of starvation as you described.

You could prevent starvation by using a different scheduler. For instance, you can say that you process at most f(priority) items in any given queue before considering item of a queue of lower priority (this is a Round-robin scheduling).

• f can be linear : f(p) = p. I process at most 4 items of priority 4 (top), then at most 3 of priority 3,..., 1 of priority 1.
• f can be exponential: f(p) = 2^(p-1). I process at most 8 items of priority 4 (top), then at most 4 of priority 3, then at most 2 of priority 2,...,1 of priority 1.

You measure this round robin using the expected frequency of execution of each priority.

Let's take the exponential case and assume there are plenty of tasks waiting on each queue. We schedule 8 top, 4 upper-middle, 2 lower-middle, 1 low, 8 top, etc... Each round has 8 + 4 + 2 + 1 = 15 tasks, so top priority tasks take 8/15 of consumer time, next 4/15, next 2/15, next 1/15.

Answer 2

Basically you're making priority a function of two variables, like pricePaid*A + waitingTime*B. That's a perfectly sensible strategy.

Suppose you're selling tickets, and the price people pay puts them into one of the queues - high, medium, low. You could look at that as a single ordered priority queue, where the priority is high, medium, or low. Within each priority group they are ordered by time, so you can consider negative time of arrival as a sub-priority, so that when you serve one, you serve the oldest one of the highest priority. That's what you're doing now. Your priority is a function of two variables, like pricePaid*A + waitingTime*B where A is so large, or B is so small, that no amount of waitingTime can compensate for somebody else having paid a higher price.

All I'm saying is, don't make A so large, or B so small. To do that, pick your data structure so that when you remove somebody from it, you always pick the one with the highest priority.

Another way to look at it: have a single priority queue, ordered by time of arrival. However, each increment of pricePaid is equivalent to having arrived some increment of time earlier. Like if somebody pays $20, it is the same as if they had only paid $10, but they arrived one week earlier. That way, people who only paid $10, but arrived two weeks earlier, would get served first.

Answer 3

The first thing to realize is that the situation you describe (some items are 'never' processed) can only arise if you simply don't have the capacity to handle the volume of requests. If you have the capacity to handle the expected volume of requests over a given time period, you will be able to handle all the requests. This is a tautology. Changing the order of the requests will not change your capacity or the volume (unless the order they are processed somehow changes the processing.)

Barring that, you might have a situation where you have a busy time of day and some lower priority transactions have to wait too long. If that's the case your model is incorrect. The structure of your current approach is correct only if the the highest priority items are always truly higher priority than the other items. Higher priority items should be processed first above lower priority items no matter what. What you are saying here is that you want to handle lower priority items before higher priority items if they are old. This implies to me that you should probably structure your prioritization based on SLAs. That is, each transaction has a expected response time. You then work the transactions based on when they are due. Your current high priority levels then translate into short SLAs and the lower priorities into longer expected response times.