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.
Best Answer
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).fcan 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.fcan 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.