Как избежать истощения источников работы с более низким приоритетом

Question

Предположим, у вас есть источники предметов для выполнения с различными приоритетами, и способность завершать предметы всегда насыщена. Как вы гарантируете, что предметы с более низким приоритетом не полностью истощены?

Я думаю, что мог бы объединить приоритет источника со временем, прошедшим с момента его последнего обслуживания, чтобы получить динамический "эффективный" приоритет. Таким образом, источники с более низким приоритетом будут медленно подниматься до тех пор, пока они не станут достаточно высокими для обслуживания.

Я не хотел изобретать велосипед здесь, по крайней мере, не спрашивая, если существует более элегантное решение этой проблемы. Спасибо!

Answer 1

То, что вы думаете, является стандартной идеей и называется старением.

Старение используется, чтобы гарантировать, что задания с более низким приоритетом в конечном итоге завершат свое выполнение. Эта техника может быть использована для уменьшения голода низко приоритетных задач. Существует множество способов реализовать устаревание, но все они имеют тот же принцип, что приоритет процесса должен увеличиваться по мере его ожидания в очереди готовности. Увеличение приоритета может или не может быть равно времени ожидания процесса.

---

Ваша текущая мысль состоит в том, чтобы назначить приоритет процессу. Обычно вы делаете это, помещая весь процесс в кучу min (или max, в зависимости от вашей реализации), а затем опрашиваете кучу...

В качестве альтернативы вы можете присвоить процессу приоритет. Вы делаете это, сохраняя несколько очередей / списков каждого типа приоритета (самый высокий, высокий, средний, низкий, самый низкий и т. Д.).

• Держите несколько очередей каждого типа;
• Получить элемент из списка наивысшего приоритета и завершить его ИЛИ назначить квант времени для каждого из процессов с высоким приоритетом в циклическом порядке;
  • Если все процессы в списке с высоким приоритетом обслуживаются, начните обслуживать процессы с более низким приоритетом до тех пор, пока что-то снова не будет добавлено в список с более высоким приоритетом;
• Как и когда любой процесс с более низкими приоритетами ожидал слишком долго, удалите его из этого списка приоритетов и добавьте его к следующему более высокому уровню приоритета.

Это тоже стандартный алгоритм преподавания в операционных системах.