Добрый день.

Встала задача реализовать очередь с приоритетами своеобразного типа: чем выше приоритет — тем чаще вызывается операция.

Пример:

Допустим существует пять операций и 10 диапазонный приоритет:

Операция 1 — 10 приоритет
Операция 2 — 8 приоритет
Операция 3 — 6 приоритет
Операция 4 — 5 приоритет
Операция 5 — 2 приоритет

В кассу должны подходить люди чаще с высоким приоритетом операции — но и иногда пропускать операции с низкими приоритетами.
Подскажите алгоритм более подходящий для живой очереди в кассу.

Здравствуйте, Аноним, Вы писали:

А>В кассу должны подходить люди чаще с высоким приоритетом операции — но и иногда пропускать операции с низкими приоритетами.

Вот это очень неопределенно. Что значит иногда ?

А вообще очень похоже на планирование потоков в Windows.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, Аноним, Вы писали:

А>>В кассу должны подходить люди чаще с высоким приоритетом операции — но и иногда пропускать операции с низкими приоритетами.

PD>Вот это очень неопределенно. Что значит иногда ?

Ну представьте ситуацию когда стоит огромная очередь в кассу и кассир вызывает людей по одному. В данном случае к кассиру чаще должны подходить люди с большим приоритетом, но также, нужно обслуживать людей с меньшим приоритетом — просто реже!

PD>А вообще очень похоже на планирование потоков в Windows.

Похоже — но там реализация другая. Чем меньше приоритет — тем дается меньше кванта времени на исполнение потоку. Но направление верное — только как мне можно это реализовать?

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

Здравствуйте, deniok, Вы писали:

D>Присваиваешь каждому "важность" — величину, изначально равную приоритету. На каждом шаге из очереди убирается персона с наибольшей важностью, а важность остальных ожидающих увеличивается на их приоритет.

Спасибо! То — что нужно!

Здравствуйте, Аноним, Вы писали:

А>Добрый день.

А>Встала задача реализовать очередь с приоритетами своеобразного типа: чем выше приоритет — тем чаще вызывается операция.

А>Пример:

А>Допустим существует пять операций и 10 диапазонный приоритет:

А>Операция 1 — 10 приоритет
А>Операция 2 — 8 приоритет
А>Операция 3 — 6 приоритет
А>Операция 4 — 5 приоритет
А>Операция 5 — 2 приоритет

А>В кассу должны подходить люди чаще с высоким приоритетом операции — но и иногда пропускать операции с низкими приоритетами.
А>Подскажите алгоритм более подходящий для живой очереди в кассу.

На сколько я понял из контекста, если идет выполнение операции, ее нельзя отменить и переключится на другую. Так? Тогда может подойти вероятностная модель.

Т.е.
Операция 1 — вероятность 10/31
Операция 2 — вероятность 8/31
Операция 3 — вероятность 6/31
Операция 4 — вероятность 5/31
Операция 5 — вероятность 2/31

Бросаем "кубик" и выбираем операцию для выполнения.

Получим что первая операция будет выполняться приблизительно каждый третий раз. А иногда будет выполняться и пятая операция.

Здравствуйте, Аноним, Вы писали:

А>Похоже — но там реализация другая. Чем меньше приоритет — тем дается меньше кванта времени на исполнение потоку.

Нет. Квант дается только потокам с наивысшим приоритетом. Остальным — ничего.

>Но направление верное — только как мне можно это реализовать?

Задачи с наивысшим приоритетом — в начало очереди (списка).

А задачи с низким приоритетом — как в Windows

Imagine the following situation: you've got a priority 7 thread that's running, preventing a priority 4 thread from ever receiving CPU time; however, a priority 11 thread is waiting on some resource that the priority 4 thread has locked. But because the priority 7 thread in the middle is eating up all the CPU time, the priority 4 thread will never run long enough to finish whatever it's doing and release the resource blocking the priority 11 thread. What does Windows 2000 do to address this situation? Once per second, the balance set manager (a system thread that exists primarily to perform memory management functions and is described in more detail in Chapter 7) scans the ready queues for any threads that have been in the ready state (that is, haven't run) for longer than 300 clock ticks (approximately 3 to 4 seconds, depending on the clock interval). If it finds such a thread, the balance set manager boosts the thread's priority to 15 and gives it double the normal quantum. Once the 2 quantums are up, the thread's priority decays immediately to its original base priority. If the thread wasn't finished and a higher priority thread is ready to run, the decayed thread will return to the ready queue, where it again becomes eligible for another boost if it remains there for another 300 clock ticks.

Здравствуйте, Аноним, Вы писали:

А>Допустим существует пять операций и 10 диапазонный приоритет:

А>Операция 1 — 10 приоритет
А>Операция 2 — 8 приоритет
А>Операция 3 — 6 приоритет
А>Операция 4 — 5 приоритет
А>Операция 5 — 2 приоритет

А>В кассу должны подходить люди чаще с высоким приоритетом операции — но и иногда пропускать операции с низкими приоритетами.
А>Подскажите алгоритм более подходящий для живой очереди в кассу.
помнится, для своих служебных задач реализовал это так (просто и быстро, с похожим на правду результатом):
1) Сложим все приоритеты, получим число 31
2) сделаем массив длиной 31 элемент и заполним его числами от 1 до 5, количество — берем из приоритетов (то есть 10 единиц, 5 четверок....)
3) перемешали массив
4) проходим по массиву, элемент — это номер текущей операции.

Распределение операций получается не особо хорошее, но уже от задачи зависит, критично ли оно там. Мне было не критично.

Здравствуйте, Аноним, Вы писали:

Можно на каждый приоритет создать свою очередь, всего 10 очередей. Определить правило: из 0-й очереди берем n0 заданий, затем из 1-й очереди берем n1 заданий, и т.д. по кругу.

Здравствуйте, Аноним, Вы писали:

А>Ну представьте ситуацию когда стоит огромная очередь в кассу и кассир вызывает людей по одному. В данном случае к кассиру чаще должны подходить люди с большим приоритетом, но также, нужно обслуживать людей с меньшим приоритетом — просто реже!

Не совсем "очередь в кассу", потому что сразу после обслуживания человек встанет в очередь заново.

Подход номер 1, сглаживающий социальное неравенство.

Пусть очередь представлена линейным списком.
Определим такое правило вставания в очередь: человек с приоритетом P находит последнего с приоритетом P (или более высоким) и встаёт не сразу за ним, а за следующим после него.

Например, у нас есть три кшатрия "A", пять вайшьи "b" и два шудры "~"

     A1 A2 A3 b1 b2 b3 b4 b5 ~1 ~2     исходная очередь - в порядке главенства
A1 : A2 A3 b1    b2 b3 b4 b5 ~1 ~2 :   A1 обслуживается и встаёт через одного после A3, т.е. после b1
A2 : A3 b1 A1 b2    b3 b4 b5 ~1 ~2 :
A3 : b1 A1 b2 A2 b3    b4 b5 ~1 ~2 :
b1 : A1 b2 A2 b3 A3 b4 b5 ~1    ~2 :   b1 встаёт через одного после b5, т.е. после ~1
A1 : b2 A2 b3 A3 b4    b5 ~1 b1 ~2 :
b2 : A2 b3 A3 b4 A1 b5 ~1 b1 ~2    :
A2 : b3 A3 b4 A1 b5    ~1 b1 ~2 b2 :
b3 : A3 b4 A1 b5 A2 ~1 b1 ~2 b2    :
A3 : b4 A1 b5 A2 ~1    b1 ~2 b2 b3 :
b4 : A1 b5 A2 ~1 A3 b1 ~2 b2 b3    :
A1 : b5 A2 ~1 A3 b1    ~2 b2 b3 b4 :
b5 : A2 ~1 A3 b1 A1 ~2 b2 b3 b4    :
A2 : ~1 A3 b1 A1 ~2    b2 b3 b4 b5 :
~1 : A3 b1 A1 ~2 A2 b2 b3 b4 b5    :
A3 : b1 A1 ~2 A2 b2    b3 b4 b5 ~1 :
b1 : A1 ~2 A2 b2 A3 b3 b4 b5 ~1    :
A1 : ~2 A2 b2 A3 b3    b4 b5 ~1 b1 :
~2 : A2 b2 A3 b3 A1 b4 b5 ~1 b1    :
A2 : b2 A3 b3 A1 b4    b5 ~1 b1 ~2 :
b2 : A3 b3 A1 b4 A2 b5 ~1 b1 ~2    :
A3 : b3 A1 b4 A2 b5    ~1 b1 ~2 b2 :
b3 : A1 b4 A2 b5 A3 ~1 b1 ~2 b2    :
A1 : b4 A2 b5 A3 ~1    b1 ~2 b2 b3 :
b4 : A2 b5 A3 ~1 A1 b1 ~2 b2 b3    :
A2 : b5 A3 ~1 A1 b1    ~2 b2 b3 b4 :
b5 : A3 ~1 A1 b1 A2 ~2 b2 b3 b4    :
A3 : ~1 A1 b1 A2 ~2    b2 b3 b4 b5 :
~1 : A1 b1 A2 ~2 A3 b2 b3 b4 b5    :
A1 : b1 A2 ~2 A3 b2    b3 b4 b5 ~1 :
b1 : A2 ~2 A3 b2 A1 b3 b4 b5 ~1    :

A1 => 6
A2 => 5
A3 => 5

b1 => 3
b2 => 2
b3 => 2
b4 => 2
b5 => 2

~1 => 2
~2 => 1

Подход номер 2:
Опять линейный список. Находим последний элемент с большим-или-равным приоритетом, а также k-ый элемент с меньшим приоритетом.
Встаём за тем, который дальше. То есть, обязательно пропускаем перед собой k младших.

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