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 deque
s).
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.