6

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.

7
  • Thanks for the edit: indeed, it looked quite unprofessional.
    – elmazzun
    Jul 13, 2016 at 13:59
  • 3
    Did you define a discipline that seems correct in your case? That is, I can imagine a case when ignoring low-priority queues while the high-priority queue is full is exactly the correct behavior: think of your priority email inbox. Until you define what's correct in your case, it's hard to see if any specific solution may be correct.
    – 9000
    Jul 13, 2016 at 14:01
  • why did you have four priority levels in the first place?
    – UmNyobe
    Jul 13, 2016 at 15:34
  • You might be interested in LMAX's Disruptor Pattern. Dealing with starvation of the kind you're describing is one of its design goals. Jul 15, 2016 at 16:23
  • I'm confused by your example. It doesn't show a situation where anything beyond the most naive approach is necessary. i.e. it doesn't illustrate the problem you are describing in your question.
    – JimmyJames
    Jul 15, 2016 at 16:38

3 Answers 3

8

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.

5
  • Basically, you are suggesting to not deal with starvation with my controller thread, but to remove it totally by reformulating the removal policy of my consumer thread?
    – elmazzun
    Jul 14, 2016 at 8:24
  • yes indeed...........
    – UmNyobe
    Jul 14, 2016 at 8:38
  • There are interesting effects when there are fewer than half as many tasks of one prority as the next higher priority... Jul 14, 2016 at 13:28
  • @UmNyobe, I updated the question with an output of your implementation.
    – elmazzun
    Jul 15, 2016 at 10:04
  • 1
    If the max priority queue is 'always' full, and you have requests in other queues, your processing must inherently fall behind. By switching to lower priority requests, you are ignoring the higher priority requests which, presumably, will keep coming. If that's what is going to happen (and it's not clear that there is a real problem to solve), you either have to determine which requests will not be processed, increase your capacity, or reduce the volume of requests. If you don't do these things, your application will continually fall behind and unprocessed messages will pile up.
    – JimmyJames
    Jul 15, 2016 at 16:31
3

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.

1
  • I'm not sure I understood pricePaid*A + waitingTime*B, could you expand your answer please?
    – elmazzun
    Jul 14, 2016 at 8:38
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.