Способ и устройство для управления очередями
Изобретение относится к области связи. Техническим результатом является поддержка любого количества очередей при планировании и поддержка увеличения количества очередей без изменения логического ядра аппаратной реализации. В вариантах осуществления настоящего изобретения раскрыты способ и устройство для планирования очередей. Способ включает в себя индексирование одной или большего количества очередей с использованием первого циркуляционного связанного списка; обращение к одной или, соответственно, большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка; и принятие величины, полученной вычитанием значения единицы планирования в начале очереди из среднего значения весового коэффициента каждой очереди, в качестве остаточного среднего значения весового коэффициента этой очереди; удаление одной очереди из первого циркуляционного связанного списка и обновление среднего значения весового коэффициента как суммы заданного значения весового коэффициента и остаточного среднего значения весового коэффициента этой очереди, если среднее значение весового коэффициента этой очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди; и включение очереди, удаленной из первого циркуляционного связанного списка, во второй циркуляционный связанный список. 2 н. и 8 з.п. ф-лы, 9 ил.
Область техники, к которой относится изобретение
Настоящее изобретение относится к области связи и, в частности, к способу и устройству для управления очередями.
Уровень техники
Традиционным алгоритмом планирования очередей с использованием весовых коэффициентов является весовая циклическая диспетчеризация (WRR, Weighted Round Robin) и схема планирования с использованием WRR в соответствии с уровнем техники приведена на фиг.2. Как показано на фиг.2, при постановке в очередь сообщение сначала относят к очереди определенного приоритета, соответствующего приоритету сообщения. При осуществлении планирования выбираются очереди с различными приоритетами в соответствии со способом опроса. Количество сообщений, отправленных в каждом цикле, пропорционально весовому коэффициенту очереди.
При планировании с использованием WRR каждый порт обслуживает множество выходных очередей. Эти очереди, в свою очередь, планируются таким образом, чтобы обеспечить определенное время обслуживания каждой очереди. При этом каждой очереди назначается весовой коэффициент, и его значение представляет собой долю ресурсов, выделенных для этой очереди. Например, при использовании порта с пропускной способностью 100 Мбитов в секунду значения весовых коэффициентов для алгоритмов планирования очередей с использованием WRR, назначенные порту, составляют 50, 30, 10 и 10, так что очереди с низшим приоритетом гарантируется как минимум полоса, соответствующая пропускной способности 10 Мбитов в секунду, что позволяет избежать ситуации, когда сообщениям в очереди с низким приоритетом обслуживание может не предоставляться в течение длительного времени, если используется планирование на основе строгих приоритетов.
Очевидно, что средствами алгоритмов с использованием только WRR сложно поддерживать потоки переменной длины, в особенности неожиданные потоки. В результате появились алгоритмы дефицитной весовой циклической диспетчеризации (DWRR, Deficit Weighted Round Robin).
На фиг.3 представлена схема планирования с использованием DWRR в соответствии с уровнем техники и, как видно на фиг.3, каждой очереди задано значение W весового коэффициента и среднее значение DC весового коэффициента, при этом среднее значение DC весового коэффициента меньше или равно значению весового коэффициента. Планировщик обращается к каждой непустой очереди, и если длина пакета в начале этой очереди больше значения DC, то планировщик переходит к следующей очереди. Если длина пакета в начале этой очереди меньше или равна значению DC, то пакет передается на выходной порт, а переменная DC уменьшается на количество байтов длины этого пакета. Планировщик непрерывно передает пакеты на выход и уменьшает значение DC до тех пор, пока длина пакета в начале этой очереди не станет больше значения переменной DC, а остаточное значение DC используется как разрешающее значение, сохраняемое для следующего опроса. Если очередь пуста, значение DC задается равным нулю и планировщик обслуживает следующую непустую очередь.
Алгоритм DWRR способен поддерживать планирование для сообщений переменной длины и с технической точки зрения имеет очень хорошие перспективы применения. Однако аппаратная реализация, в особенности способа, поддерживающего простое увеличение количества очередей, без изменения логического ядра аппаратной реализации, является в настоящее время объектом исследований. Для обычных способов реализации на основе двоичного дерева поддержка большого количества очередей вызывает значительные трудности, и при необходимости изменения логики ядра для увеличения количества очередей сложность разработки возрастает.
В настоящее время не предложено эффективных решений проблемы, связанной со сложностью поддержки увеличения количества очередей, а также со сложностью реализации модуля планирования с использованием DWRR с меньшим потреблением ресурсов при условии, что логическое ядро аппаратной реализации не изменяется.
Раскрытие изобретения
Настоящее изобретение сделано в свете проблемы, связанной со сложностью поддержки увеличения количества очередей, а также со сложностью реализации модуля планирования с использованием DWRR с меньшим потреблением ресурсов при условии, что логическое ядро аппаратной реализации не изменяется. Таким образом, основной целью настоящего изобретения является обеспечение способа планирования очередей и устройства для решения указанных выше проблем.
Для достижения указанной выше цели в соответствии с одним аспектом настоящего изобретения предложен способ планирования очередей.
Способ планирования очередей в соответствии с настоящим изобретением включает в себя следующие шаги: индексирование одной или большего количества очередей с использованием первого циркуляционного связанного списка; обращение к одной или, соответственно, большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка; и принятие величины, полученной вычитанием значения единицы планирования в начале очереди из среднего значения весового коэффициента каждой очереди, в качестве остаточного среднего значения весового коэффициента этой очереди; удаление одной очереди из первого циркуляционного связанного списка и обновление среднего значения весового коэффициента как суммы заданного значения весового коэффициента и остаточного среднего значения весового коэффициента этой очереди, если среднее значение весового коэффициента этой очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди; и включение очереди, удаленной из первого циркуляционного связанного списка, во второй циркуляционный связанный список.
Предпочтительно способ также может включать в себя следующий шаг: постоянное обращение к одной или большему количеству очередей в соответствии с первым циркуляционным связанным списком, если в первом циркуляционном связанном списке присутствует одна очередь, среднее значение весового коэффициента которой не меньше единицы планирования в начале этой очереди.
Предпочтительно индексирование одной или большего количества очередей с использованием первого циркуляционного связанного списка включает в себя следующие шаги: задание весовых коэффициентов для одной или большего количества очередей; и первоначальное назначение средних значений весовых коэффициентов одной или большего количества очередей равными значениям заданных весовых коэффициентов, заданного значения равным нулю, состояния очереди соответствующим пустой очереди, а флага связи имеющим значение «не связан».
Предпочтительно обращение к одной или, соответственно, большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка и вычитание значения единицы планирования в начале очереди из среднего значения весового коэффициента каждой очереди включает в себя следующие шаги: считывание начального указателя первого циркуляционного связанного списка, определение текущего номера планируемой очереди по начальному указателю и обращение к первому циркуляционному связанному списку с использованием начального указателя первого циркуляционного связанного списка в качестве адреса; и вычитание значения единицы планирования в начале этой очереди из среднего значения весового коэффициента, если состояние текущей планируемой очереди соответствует непустой очереди и среднее значение весового коэффициента больше или равно значению единицы планирования в начале этой очереди.
Предпочтительно способ также включает в себя следующие шаги: считывание конечного указателя первого циркуляционного связанного списка, обращение к текущей планируемой очереди с использованием конечного указателя первого циркуляционного связанного списка в качестве адреса и запись начального указателя первого циркуляционного связанного списка в позицию указателя следующего шага; обновление конечного указателя первого циркуляционного связанного списка с использованием начального указателя первого циркуляционного связанного списка; и обращение к очереди с использованием начального указателя первого циркуляционного связанного списка в качестве адреса для получения указателя следующего шага с целью обновления начального указателя первого циркуляционного связанного списка.
Предпочтительно удаление очереди из первого циркуляционного связанного списка, если среднее значение весового коэффициента очереди в этом связанном списке меньше единицы планирования в начале этой очереди, дополнительно включает в себя следующий шаг: удаление очереди из первого циркуляционного связанного списка и отсутствие добавления очереди во второй циркуляционный связанный список, если состояние очереди указано как пустая очередь.
Предпочтительно способ также включает в себя следующие шаги: удаление очереди из первого циркуляционного связанного списка и последующее добавление этой очереди в конец второго циркуляционного связанного списка, если состояние очереди соответствует непустой очереди и среднее значение весового коэффициента меньше значения единицы планирования в начале этой очереди.
Предпочтительно добавление очереди, удаленной из первого циркуляционного связанного списка, во второй циркуляционный связанный список включает в себя следующий шаг: добавление очереди во второй циркуляционный связанный список, если состояние очереди изменяется с пустой очереди на непустую очередь и флаг связи имеет значение «не связан».
Предпочтительно способ также включает в себя следующий шаг: первый циркуляционный связанный список и второй циркуляционный связанный список меняются местами, если первый циркуляционный связанный список пуст.
Для достижения указанной выше цели в соответствии с другим аспектом настоящего изобретения предложено устройство для планирования очередей.
Указанное устройство содержит: первый циркуляционный связанный список и второй циркуляционный связанный список, оба использующие структуру однонаправленного связанного списка; начальный указатель первого циркуляционного связанного списка и конечный указатель первого циркуляционного связанного списка, а также одну или большее количество очередей, связанных в циркуляционную структуру; начальный указатель второго циркуляционного связанного списка и конечный указатель второго циркуляционного связанного списка, а также одну или большее количество очередей, связанных в циркуляционную структуру, при этом очереди связаны друг с другом посредством указателей, и если среднее значение весового коэффициента очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди, эта очередь удаляется из первого циркуляционного связанного списка и добавляется во второй циркуляционный связанный список; и если первый циркуляционный связанный список пуст, первый циркуляционный связанный список и второй циркуляционный связанный список меняются местами.
В настоящем изобретении использован способ индексирования одной или большего количества очередей с использованием первого циркуляционного связанного списка; обращения к одной или, соответственно, большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка и вычитания значения единицы планирования в начале очереди из среднего значения весового коэффициента каждой очереди; удаления одной очереди первого циркуляционного связанного списка и обновления среднего значения весового коэффициента как суммы заданного значения весового коэффициента и остаточного среднего значения весового коэффициента, если среднее значение весового коэффициента этой очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди; и включения очереди, удаленной из первого циркуляционного связанного списка, во второй циркуляционный связанный список. Настоящее изобретение решает проблему, связанную со сложностью поддержки увеличения количества очередей и со сложностью реализации модуля планирования с использованием DWRR с меньшим потреблением ресурсов с целью обеспечения возможности поддержки любого количества очередей при планировании и поддержки увеличения количества очередей при условии, что логическое ядро аппаратной реализации не изменяется.
Краткое описание чертежей
Приложенные чертежи обеспечивают лучшее понимание настоящего изобретения и составляют часть настоящей заявки. Иллюстративные варианты осуществления и их описание использованы для объяснения настоящего изобретения без необоснованного ограничения объема настоящего изобретения. На чертежах:
фиг.1 представляет собой схему последовательности действий способа планирования в соответствии с вариантами осуществления настоящего изобретения;
фиг.2 представляет собой схему планирования с использованием WRR в соответствии с уровнем техники;
фиг.3 представляет собой схему планирования с использованием DWRR в соответствии с уровнем техники;
фиг.4 представляет собой схему связанного списка очереди в соответствии с вариантами осуществления настоящего изобретения;
фиг.5 представляет собой схему связей между начальными/конечными указателями в активном/неактивном состоянии и очередями в соответствии с вариантами осуществления настоящего изобретения;
фиг.6 представляет собой схему устройства планирования в соответствии с вариантами осуществления настоящего изобретения;
фиг.7 представляет собой схему активного связанного списка группы очередей в соответствии с вариантами осуществления настоящего изобретения;
фиг.8 представляет собой схему обновления активного связанного списка в соответствии с вариантами осуществления настоящего изобретения; и
фиг.9 представляет собой схему обновления неактивного связанного списка в соответствии с вариантами осуществления настоящего изобретения.
Осуществление изобретения
Учитывая сложность поддержки увеличения количества очередей и сложность практической реализации модуля планирования с использованием DWRR с меньшим потреблением ресурсов при условии, что логическое ядро аппаратной реализации не изменяется, варианты осуществления настоящего изобретения реализуют способ и устройство для управления очередями. Указанный способ включает в себя следующие шаги: индексирование одной или большего количества очередей с использованием первого циркуляционного связанного списка; обращение к одной или большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка и вычитание значения единицы планирования в начале каждой очереди из среднего значения весового коэффициента одной очереди; удаление одной очереди из первого циркуляционного связанного списка и обновление среднего значения весового коэффициента как суммы заданного значения весового коэффициента и остаточного среднего значения весового коэффициента, если среднее значение весового коэффициента этой очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди; и включение очереди, удаленной из первого циркуляционного связанного списка, во второй циркуляционный связанный список.
Следует отметить, что варианты осуществления настоящего изобретения и их признаки могут сочетаться друг с другом, если не возникает противоречия. Далее со ссылкой на чертежи приведено подробное описание вариантов осуществления настоящего изобретения.
Сложность реализации устройства планирования обычно существенно увеличивается с ростом количества планируемых очередей, причем это увеличение носит нелинейный характер. Проводимые в настоящее время исследования в области алгоритмов планирования направлены на поддержку как можно большего количества очередей. В настоящем изобретении предложен способ реализации с характеристиками, соответствующими алгоритмам DWRR, и с использованием попеременного переключения активного связанного списка и неактивного связанного списка с целью поддержки планирования любого количества очередей. Благодаря настоящему изобретению реализован алгоритм комплексного планирования с использованием простого действия над связанными списками, основанного на обращении к хранилищу, путем связывания всех очередей, подлежащих планированию, в два однонаправленных связанных списка. При увеличении количества планируемых очередей лишь линейно возрастает объем хранилища связанных списков, а логику алгоритма и структуру данных менять не требуется, что дает выигрыш при увеличении количества очередей.
В настоящем изобретении циклическое обновление активного связанного списка и неактивного связанного списка, в частности, означает, что функцией устройства планирования является определение количества обслуживаемых очередей в каждом периоде планирования и использование весового коэффициента Wi для обозначения количества обслуживании, назначаемых в цикле планирования. Например, как показано на фиг.7, имеется шесть очередей, A-F, весовые коэффициенты отдельных очередей обозначены соответственно WA-WF, и остаточные значения, соответствующие оставшимся без обслуживания частям очередей, обозначены DCA-DCF.
Фиг.7 представляет собой схему активного связанного списка группы очередей в соответствии с вариантами осуществления настоящего изобретения; фиг.8 представляет собой схему обновления активного связанного списка в соответствии с вариантами осуществления настоящего изобретения; и фиг.9 представляет собой схему обновления неактивного связанного списка в соответствии с вариантами осуществления настоящего изобретения. После обслуживания каждой очереди размер (Psize) первого пакета, стандартизованный в соответствии с количеством обслуживании (т.е. Psize является динамической величиной и представляет собой размер пакета в начале очереди), вычитается из значения DCi очереди. Таким образом, размер первого пакета представляет собой единицу планирования. Для упрощения описания количество обслуживании для каждой очереди в иллюстративной группе очередей может быть уменьшено до 1. Если значение DCi очереди оказывается меньшим Psize, такая очередь удаляется из активного связанного списка, что обеспечивает возможность предоставления обслуживания всем очередям в активном связанном списке, и добавляется в конец неактивного связанного списка, при этом значение DCi устанавливается равным сумме весового коэффициента Wi и остаточного значения DCi.
Если активный связанный список пуст, это означает, что текущий цикл завершен. Активный связанный список и неактивный связанный список меняются местами для начала нового цикла.
В соответствии с вариантами осуществления настоящего изобретения реализован способ планирования очередей. Фиг.1 представляет собой схему последовательности действий способа планирования в соответствии с вариантами осуществления настоящего изобретения, включающего в себя шаги c S102 по S108.
На шаге S102 одна или большее количество очередей индексируется с использованием первого циркуляционного связанного списка.
На шаге S104 происходит обращение к одной или, соответственно, большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка, и значение, получаемое вычитанием значения единицы планирования в начале очереди из среднего значения весового коэффициента каждой очереди, принимается в качестве остаточного среднего значения весового коэффициента этой очереди.
На шаге S106 происходит удаление одной очереди из первого циркуляционного связанного списка и обновление среднего значения весового коэффициента как суммы заданного значения весового коэффициента и остаточного среднего значения весового коэффициента этой очереди, если среднее значение весового коэффициента этой очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди.
На шаге S108 происходит включение очереди, удаленной из первого циркуляционного связанного списка, во второй циркуляционный связанный список.
Предпочтительно указанный выше способ также включает в себя следующие шаги.
На шаге S110 первый циркуляционный связанный список и второй циркуляционный связанный список меняются местами, если первый циркуляционный связанный список пуст; и выполняется следующий цикл.
Указанные выше шаги с S104 по S110 представляют собой процесс циркуляции, происходящий в циркуляционном связанном списке.
Далее подробно описана практическая реализация данного варианта осуществления настоящего изобретения.
В частности, в способе планирования выполняются следующие действия.
Инициализация связанного списка
На шаге S102 после задания пользователем весовых коэффициентов всех очередей начинается процесс инициализации. После инициализации значения DC всех очередей равны значениям весовых коэффициентов, Psize равен 0, состояние очереди соответствует пустой очереди, флаг связи имеет значение «не связан», а содержимое указателя следующего шага не имеет значения.
Движение очереди
На шаге S104 считывается начальный указатель активного связанного списка для определения порядкового номера текущей планируемой очереди.
Значение начального указателя активного связанного списка используется в качестве адреса для обращения к хранилищу связанных списков очередей, а значение DC обновляется как результат вычитания значения Psize из исходного значения DC, если состояние очереди соответствует непустой очереди и значение DC больше или равно значению Psize.
Далее считывается конечный указатель активного связанного списка и значение конечного указателя активного связанного списка используется в качестве адреса для обращения к хранилищу связанных списков очередей, а значение начального указателя активного связанного списка записывается в позицию указателя следующего шага.
Конечный указатель активного связанного списка обновляется с использованием значения начального указателя активного связанного списка.
Для получения указателя следующего шага производится обращение к хранилищу связанных списков очередей с использованием значения начального указателя активного связанного списка в качестве адреса, таким образом производится обновление исходного начального указателя активного связанного списка.
Добавление очереди
На шаге S108, если состояние очереди изменяется с пустой на непустую и флаг связи имеет значение «не связан», то данная очередь добавляется в конец неактивного связанного списка.
Удаление очереди
На шаге S106, если очередь подлежит планированию, т.е. если начальный указатель активного связанного списка в DWRR указывает на данную очередь, определяется состояние очереди. Если состояние очереди соответствует пустой очереди, то запускается операция удаления связи, т.е. происходит удаление очереди из активного связанного списка и очередь не добавляется в неактивный связанный список. После удаления очереди из связанного списка флаг связи снимается.
Если состояние очереди соответствует непустой очереди, но ее значение DC меньше значения Psize, то это означает, что очередь определена кандидатом на обслуживание в текущем цикле, и данная очередь удаляется из активного связанного списка и добавляется в конец неактивного связанного списка. Одновременно значение DC очереди обновляется как сумма ее весового коэффициента и остаточного значения DC.
Смена мест связанных списков
На шаге S110, если активный связанный список пуст, т.е. если начальный указатель активного связанного списка и конечный указатель активного связанного списка совпадают и указывают на текущую планируемую очередь, это означает, что текущий цикл планирования завершен и активный связанный список и неактивный связанный список меняются местами.
В соответствии с вариантами осуществления настоящего изобретения реализовано устройство для управления очередями. Данное устройство содержит: первый циркуляционный связанный список и второй циркуляционный связанный список, оба использующие структуру однонаправленного связанного списка; начальный указатель первого циркуляционного связанного списка и конечный указатель первого циркуляционного связанного списка, а также одну или большее количество очередей, связанных в циркуляционную структуру; начальный указатель второго циркуляционного связанного списка и конечный указатель второго циркуляционного связанного списка, а также одну или большее количество очередей, связанных в циркуляционную структуру, при этом очереди связаны друг с другом посредством указателей, и если среднее значение весового коэффициента очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди, эта очередь удаляется из первого циркуляционного связанного списка и добавляется во второй циркуляционный связанный список; и если первый циркуляционный связанный список пуст, то первый циркуляционный связанный список и второй циркуляционный связанный список меняются местами, т.е. первый циркуляционный связанный список становится вторым циркуляционным связанным списком, а второй циркуляционный связанный список становится первым циркуляционным связанным списком.
Фиг.5 представляет собой схему связей между головными/конечными указателями в активном/неактивном состоянии и очередями в соответствии с вариантами осуществления настоящего изобретения. Информация, подлежащая сохранению для каждой очереди, помимо весового коэффициента, значения DC и указателя следующего шага, также содержит состояние очереди, размер первого пакета и флаг связи. Состояние очереди указывает, является ли очередь в данный момент пустой или непустой; размер первого пакета обозначает длину пакета первого сообщения в текущей очереди и представляет собой единицу планирования; флаг связи указывает, добавлена ли очередь в связанный список очередей DWRR.
Фиг.6 представляет собой схему устройства планирования в соответствии с вариантами осуществления настоящего изобретения. Данное устройство планирования очередей, реализованное в соответствии с настоящим изобретением, встроено в устройство обмена данными или в устройство управления трафиком, основанное на механизме коммутации с промежуточным хранением. Таким образом, данное устройство включает в себя коммутационное устройство, устройство маршрутизации и передающее устройство, но не ограничивается ими.
Как ясно из вышеприведенного описания, настоящее изобретение позволяет поддерживать любое количество очередей при планировании и поддерживает увеличение количества очередей при условии, что логическое ядро аппаратной реализации не изменяется.
Приведенное выше описание представляет собой лишь иллюстрацию предпочтительных вариантов осуществления настоящего изобретения и не ограничивает настоящее изобретение. Специалисту в данной области техники очевидно, что настоящее изобретение может содержать различные изменения и замены. Любые изменения, эквивалентные замены, усовершенствования и т.д. в пределах сущности настоящего изобретения включены в объем охраны, определенный формулой настоящего изобретения.
1. Способ планирования очередей, включающий в себя следующие шаги: индексируют одну или большее количество очередей с использованием первого циркуляционного связанного списка;
обращаются к одной или, соответственно, большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка и значение, полученное вычитанием значения единицы планирования в начале каждой очереди из среднего значения весового коэффициента этой очереди, определяют в качестве остаточного среднего значения весового коэффициента этой очереди;
удаляют одну очередь из первого циркуляционного связанного списка и обновляют среднее значение весового коэффициента как суммы заданного значения весового коэффициента и остаточного среднего значения весового коэффициента этой очереди, если среднее значение весового коэффициента этой очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди; и
включают очередь, удаленную из первого циркуляционного связанного списка, во второй циркуляционный связанный список.
2. Способ по п. 1, отличающийся тем, что дополнительно включает в себя следующий шаг:
постоянно обращаются к одной или большему количеству очередей в соответствии с первым циркуляционным связанным списком, если в первом циркуляционном связанном списке присутствует одна очередь, среднее значение весового коэффициента которой не меньше единицы планирования в начале этой очереди.
3. Способ по п. 1, отличающийся тем, что индексирование одной или большего количества очередей с использованием первого циркуляционного связанного списка включает в себя следующие шаги:
задают весовые коэффициенты для одной или большего количества очередей; и первоначально назначают среднее значение весового коэффициента одной или большего количества очередей равным значению весового коэффициента, заданное значение равным нулю, состояние очереди соответствующим пустой очереди, а флаг связи имеющим значение «не связан».
4. Способ по п. 1, отличающийся тем, что обращение к одной или большему количеству очередей с использованием начального указателя первого циркуляционного связанного списка и вычитание значения единицы планирования в начале очереди из среднего значения весового коэффициента каждой очереди включает в себя следующие шаги:
считывают начальный указатель первого циркуляционного связанного списка, определяют порядковый номер текущей планируемой очереди по начальному указателю и обращаются к первому циркуляционному связанному списку с использованием начального указателя первого циркуляционного связанного списка в качестве адреса; и
вычитают значение единицы планирования в начале текущей планируемой очереди из среднего значения весового коэффициента, если состояние текущей планируемой очереди соответствует непустой очереди и среднее значение весового коэффициента больше или равно значению единицы планирования в начале текущей планируемой очереди.
5. Способ по п. 4, отличающийся тем, что дополнительно включает в себя следующие шаги:
считывают конечный указатель первого циркуляционного связанного списка, обращаются к текущей планируемой очереди с использованием конечного указателя первого циркуляционного связанного списка в качестве адреса и записывают начальный указатель первого циркуляционного связанного списка в позицию указателя следующего шага;
обновляют конечный указатель первого циркуляционного связанного списка с использованием начального указателя первого циркуляционного связанного списка; и
обращаются к очереди с использованием начального указателя первого циркуляционного связанного списка в качестве адреса для получения указателя следующего шага, таким образом производят обновление исходного начального указателя активного связанного списка.
6. Способ по п. 1, отличающийся тем, что удаление одной очереди из первого циркуляционного связанного списка, если среднее значение весового коэффициента этой очереди в этом связанном списке меньше единицы планирования в начале этой очереди, дополнительно включает в себя следующий шаг:
удаляют очередь из первого циркуляционного связанного списка и не добавляют очередь во второй циркуляционный связанный список, если состояние очереди соответствует пустой очереди.
7. Способ по п. 6, отличающийся тем, что дополнительно включает в себя следующий шаг:
удаляют очередь из первого циркуляционного связанного списка и затем добавляют эту очередь в конец второго циркуляционного связанного списка, если состояние этой очереди соответствует непустой очереди и среднее значение весового коэффициента меньше значения единицы планирования в начале этой очереди.
8. Способ по п. 1, отличающийся тем, что добавление очереди, удаленной из первого циркуляционного связанного списка, во второй циркуляционный связанный список включает в себя следующий шаг:
добавляют эту очередь во второй циркуляционный связанный список, если состояние этой очереди изменяется с пустой очереди на непустую очередь и флаг связи имеет значение «не связан».
9. Способ по любому из пп. 1-8, отличающийся тем, что дополнительно включает в себя следующий шаг:
меняют местами первый циркуляционный связанный список и второй циркуляционный связанный список, если первый циркуляционный связанный список пуст.
10. Устройство для планирования очередей, содержащее:
запоминающее устройство, в котором хранится первый циркуляционный связанный список и второй циркуляционный связанный список, оба использующие структуру однонаправленного списка, при этом в запоминающем устройстве имеется начальный указатель первого циркуляционного связанного списка и конечный указатель первого циркуляционного связанного списка, а также одну или большее количество очередей, связанных в циркуляционную структуру, в запоминающем устройстве также имеется начальный указатель второго циркуляционного связанного списка и конечный указатель второго циркуляционного связанного списка, а также одну или большее количество очередей, связанных в циркуляционную структуру, очереди связаны друг с другом посредством указателей;
процессор, обеспечивающий возможность удаления очереди из первого циркуляционного связанного списка и добавления ее во второй циркуляционный связанный список, если среднее значение весового коэффициента этой очереди в первом циркуляционном связанном списке меньше единицы планирования в начале этой очереди; и возможность смены мест первого циркуляционного связанного списка и второго циркуляционного связанного списка, если первый циркуляционный связанный список пуст.
