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