Предотвращение голодания в приоритетной очереди
Как известно, очередь с приоритетами может создавать голод для элементов с более низким приоритетом в простейшей форме. Например, предположим, что у нас есть следующие элементы в очереди с приоритетами в порядке возрастания приоритетов:
Item Priority
--------------------
Item A 0 //Lowest priority
Item B 1
Item C 2
Item D 3
Item E 4 //Highest priority
Теперь, если мы получим последовательный поток элементов с более высоким приоритетом в нашей очереди приоритетов (BE), мы никогда не сможем обрабатывать пакеты с более низким приоритетом (A). Интересно, какие существуют алгоритмы для решения этой проблемы?
Простой подход, который приходит мне в голову, - это ограничение обработки разных типов элементов в зависимости от приоритета. Например, мы ограничиваем обработку пакетов каждого типа 2 ^ priority, Так для таблицы выше, после передачи 16 предметов Item E типа, мы будем обрабатывать до 8 элементов типа Item Dдо 4 Item Cдо 2 Item B и до 1 из Item A прежде чем начать обрабатывать Item E снова. Это предотвратит голодание для разных типов предметов.
Это простой метод, но мне интересно, есть ли другие известные алгоритмы для решения этой проблемы. Любая идея для лучших алгоритмов или решений?