Дек очередь стек: Летняя школа по компьютерным наукам 2020

Летняя школа по компьютерным наукам 2020

Боковая панель

Информатикс

Перейти на…

Перейти на…[Контест] 3. Корневая декомпозиция[Контест] 5. Задачи Московской олимпиады[Липецк] День 1. Blind contestМатериалы по dfs[Контест] 1. Обход в глубину[Контест] Бинпоиск и STLРазбор контеста на STL. Задачи (G-I).[Контест] 3. Sparse Table, Дерево отрезков[Лекция] М. Прохоров | Дерево отрезков и разреженные таблицы[Лекция] 4. LCA.[Контест] 4. LCA и DSU (must-have).[Контест] 4. LCA для продвинутых.Тур с разобранными задачами Московской олимпиады[Контест] 5. Задачи Московской олимпиады[Контест] 6. Хеши[Контест] 7. Treap[Контест] 8. Вычислительная геометрия[Лекция] М. Прохоров | Вычислительная Геометрия[Контест] 1. Стек. Очередь. Дек[Контест] 2. Двоичный поиск[Контест] 3. Set и multiset[Контест] 4. Практика на сортировки[Контест] 4. Теоретические задачи на сортировку[Лекция] 5. Комбинаторика[Контест] 5. Рекурсия и комбинаторика[Лекция] 6. Динамическое программирование.[Контест] 6. Динамическое программирование.[Лекция] 7. Графы.[Контест] 7. Введение в графы.[Контест] 7. Кратчайшие пути.[Контест 8] СканлайнЯ.Лицей Итоги1. Битовые операции. Основы C++. Условный оператор. Оператор while1′. Муниципальный этап 2012 (Для решивших всё)2. Цикл for. Цикл по коллекции. Vector3. Вектор. Многомерные массивы. Функции. Рекурсия.4. Структуры данных. Стек, очередь, дек.4. Структуры данных. Стек, очередь, дек.5. Командная олимпиада6. Структуры данных: set, map6. Структуры данных: set, map7. Бинарный поиск7. Бинарный поиск8. Графы8.1 Графы. DFS. BFS8.2 Графы. Кратчайшие пути в графе9. Геометрия9. Геометрия9. Геометрия. АндрееваЛичная олимпиадаПараллель D. ИтогиВступительный контест1. Основы С++. Условный оператор2. Циклы. Массивы3. Вектор. Многомерные массивы. Функции. Рекурсия. 4. Многомерные массивы6. Структуры данных. Стек, очередь, дек.6. Структуры данных: Стек, очередь, дек.7. Структуры данных: set, map7. Структуры данных: set, map8. Бинарный поиск 8. Бинарный поиск 9.1 Графы. DFS. BFS 9.2 Графы. Кратчайшие пути в графе9. Графы

Стек и другие структуры данных

Стек и другие структуры данных — Tinkoff Generation

• Стек
• Правильные скобочные последовательности
• Обратная польская запись
• Стек в рекурсии
• Задача о наибольшем прямоугольнике
• Очередь и дек
• Односвязные и двусвязные списки

Стек

Мы уже знаем, что такое стек. Это структура данных, которая хранит элементы упорядоченно и умеет отвечать на две операции за \(O(1)\):

• push(x) — положить элемент x в конец стека
• pop() — снять и вернуть элемент, лежащий в конце стека

То есть это структура данных, где действия происходят только с элементом, лежащим в конце. Выполняется принцип FILO (First In — Last Out) — последним вынется тот элемент, который мы положили первым, если сначала положить все элементы, а потом все вынуть.

Часто для удобства у стека еще есть операции * size() — размер стека * empty() — проверка на пустоту * clear() — очистить стек

Как стек удобно использовать динамический массив: * в Питоне это list, причем push = append, pop = pop * в C++ это vector, причем push = push_back, а операция pop заменяется на две — back возвращает последний элемент, а pop_back вынимает его

a = []
a.append(5)
a.append(3)
a.append(10)
print(a.pop())
a.append(12)
print(a.pop())

10
12

Правильные скобочные последовательности

Есть несколько определений Правильной скобочной последовательности — ПСП.

1. Неформальное определение

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

Например: из выражения \((1 + 2) * (3 + 100 * (3 / 2))\) получается ПСП \(()(())\). А вот \()(())\) не получится из никакого выражения.

2. Явное определение

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

Например: \(((())())\) — ПСП, так как разбивает на вот такие непересекающиеся пары: \(\textbf{(}\underline{(}\overline{(}\overline{)}\underline{)}\textit{()}\textbf{)}\). А вот строку \((()\) нельзя разбить на пары — там нечетное число скобок.

3. Рекурсивное определение

• пустая строка — это ПСП
• если \(A\) — это ПСП, то \((A)\) — это тоже ПСП
• если \(A\) и \(B\) — это ПСП, то \(AB\) — это тоже ПСП

Например: пустая строка — ПСП, значит \(()\) — ПСП, значит \((())\) — ПСП, значит \((())()\) — ПСП, значит \(((())())\) — ПСП. А вот \(())(()\) не получится по этим правилам никак.

4. Определение через баланс ПСП — это строка из открывающих и закрывающих скобок. Давайте определим баланс на префиксе длины \(n\) как разница числа открывающих и закрывающих скобок на этом префиксе. Тогда в ПСП должны выполняться два свойства:

• любой баланс больше или равен 0
• баланс всей строки равен 0

То есть на любом префиксе открывающих скобок не меньше, чем закрывающих, а во всей строке их равное число.

Оказывается, именно последним определением удобно пользоваться, чтобы определить, является ли строка ПСП. А именно, давайте пройдемся слева направо и будем прибавлять \(+1\), если встретим открывающую скобку, и \(-1\), если встретим закрывающую скобку. И достаточно проверить, что баланс всегда неотрицателен, и равен нулю в конце.

Еще можно определить ПСП с разными видами скобок. Например, \(([](\{\}))\) — это ПСП, а \([(])\) — нет. В явное определение надо просто добавить, что скобки в одной паре должны быть одного вида. В рекурсивное определение нужно добавить правила вида “если \(A\) — это ПСП, то \([A]\) — это тоже ПСП” для всех видов скобок.

А вот определение через баланс так легко не обобщается, а ведь мы именно его хотим использовать для алгоритма проверки на ПСП. Для расширения придется использовать стек:

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

Например: строка \(\{[([])()]{}\}\). В ходе алгоритм стек будет меняться так:

Стеки, очередь, дек — когда использовать что?

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

В настоящее время я имею дело с stack/queue/deque. Я знаю, как они действуют (LIFO, FIFO, а затем декес делает это оба), но я изо всех сил пытаюсь выяснить цель.

• Для чего могут быть использованы эти 3 ADTs?
• Может ли один из них быть использован над другим для лучшего результата? Я думаю, что было бы разумно просто всегда использовать deque, поскольку он предлагает те же методы, что и queue и stack — я ошибаюсь?
• А как насчет производительности (например, скорости)? Что-нибудь, что должно быть принято во внимание при их использовании?

java

queue

deque

Поделиться

Источник

Charles    

29 апреля 2015 в 19:22

1 ответ

• Вопросы о дереве ADT в java

  У меня скоро экзамен, и одна из тем-это: Абстрактные типы данных: очередь, дек, стеки, деревья Мой вопрос: Что такое деревья? Поскольку это не интерфейс, как и 3 других, что вы думаете, подразумевается под trees? Это что-то о том, что treeset и treemap имеют общее или? Я был бы очень признателен,. ..

• Зачем использовать такие структуры данных, как очереди и стеки, если массивы проще в использовании и мощнее?

  Это может быть глупый вопрос, но он меня уже давно беспокоит. Большинство языков программирования имеют массивы (например, Java, C/C++, C#…ok Python имеет списки!) но в большей части литературы, которую я вижу, некоторые структуры данных (такие как стеки и очереди) рассматриваются как более…

3

Стеки / очереди-это базовые структуры данных, которые используются в различных областях информатики, таких как операционные системы, компьютерные сети.

Деятельность любит ЛИФО, ФИФО ЕТК. используются в различных случаях в зависимости от цели задачи, как в графе(другая структура данных), при реализации BFS использует очередь для хранения узлов, которые в дальнейшем используют базовую операцию, такую как FIFO.

И, да, скорость имеет значение. Но, мы также должны заботиться о ограничениях памяти.

P.S. Эти структуры данных и их работа могут показаться неуместными, но по мере дальнейшего изучения вы поймете, что многие великие алгоритмы основаны на них самих.

Поделиться

kartikmaji    

29 апреля 2015 в 19:27

Похожие вопросы:

Что использовать: самостоятельно или супер?

Я заворачиваю дек класса python в очередь, чтобы сделать мой код более читаемым: from collections import deque class Queue(deque): def enqueue(self,a): super(Queue, self).append(a) def…

Почему очередь std не определяет специализацию метода swap

Я читал, что все контейнеры stl обеспечивают специализацию алгоритма подкачки, чтобы избежать вызова конструктора копирования и двух операций присваивания, которые использует метод по умолчанию….

Стеки активности в android

Я все еще довольно новичок в понимании android и слышал о стеках активности. Из того, что я прочитал и понял, было то, что он создает стек по мере продвижения к каждому действию и оставляет его как…

Вопросы о дереве ADT в java

У меня скоро экзамен, и одна из тем-это: Абстрактные типы данных: очередь, дек, стеки, деревья Мой вопрос: Что такое деревья? Поскольку это не интерфейс, как и 3 других, что вы думаете,…

Зачем использовать такие структуры данных, как очереди и стеки, если массивы проще в использовании и мощнее?

Это может быть глупый вопрос, но он меня уже давно беспокоит. Большинство языков программирования имеют массивы (например, Java, C/C++, C#…ok Python имеет списки!) но в большей части литературы,…

Когда использовать очередь сообщений и когда использовать cloud background-worker

Когда я буду использовать очередь сообщений, например ironMQ, и когда я буду использовать работника обработки заданий, например ironWorker? Я только начал исследовать эти две темы, и мне трудно. ..

Python дек строк

msg = ‘afdssav’ MYQ = deque(msg) MYPQ.append(‘asdf’) Здесь я пытаюсь создать дек строк, однако, когда я поп-элементы или попытаться прочитать элементы из него с помощью Python 2.7 я получаю char по…

Как напечатать дек с конца?

Вопрос довольно прост, как мне напечатать дек, но сзади. Пример: у меня есть дек с элементами {5,4,3,2,1}. Я хочу распечатать этот дек, но начиная с последнего элемента, поэтому у меня должно быть…

Boost.Coroutine не использует сегментированные стеки

Может ли кто-нибудь дать мне пример того, как я могу использовать сегментированные стеки с boost сопрограммами? Должен ли я аннотировать каждую функцию, которая вызывается из сопрограммы со…

c# очередь и дек одновременно

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

MCQ в стеке и очереди

MCQ в структуре данных стека и очереди. Структура данных стека и очереди очень важна в информатике. В этом руководстве вы узнаете о структуре данных стека и очереди. Также вы найдете MCQ в стеке и очередях.

В моем предыдущем посте я обсуждал следующие вещи.

Программа стека на C с использованием массива.

Структура данных очереди и их реализация.

Цель этих объективных вопросов — проверить, насколько хорошо вы понимаете концепцию стека и очереди.

Стек и очередь

1. Стек и очередь представляют собой линейную структуру данных. В стеке вставки и удаления разрешены только на одном конце, поэтому он также называется LIFO (Last In First Out) .

В очереди вставка выполняется на одном конце (задний), а удаление выполняется на другом конце (передний), это также известно как FIFO (First In First Out) .

2. В стеке операция вставки известна как Push , тогда как операция удаления известна как Pop .

В очереди операция вставки известна как Enqueue , тогда как операция удаления известна как Dequeue .

Операция вставки и удаления в очереди известна как постановка в очередь и удаление из очереди .

3.

Применение стека

a) В рекурсивной функции.

б) Когда функция вызывается.

c) Преобразование выражений, например — из инфикса в постфикс, из инфикса в префикс, из постфикса в инфикс, из префикса в инфикс.

Приложение очереди

1) Обслуживание запросов единственного общего ресурса (принтер, диск, ЦП).

2) Асинхронная передача данных (данные не обязательно принимаются с той же скоростью, что и отправленные) между двумя процессами (буферы ввода-вывода), например каналы, ввод-вывод файлов, сокеты.

3) Проблема у потребителя-производителя. Когда ресурс используется несколькими потребителями. Примеры включают планирование ЦП, планирование дисков.

Вопросы по программированию в стеке

Получить минимальный элемент из стека в O (1)

Найти максимальный элемент из стека в O (1)

MCQ в стеке и очереди

Стек и очередь MCQ

Подождите, пока активность загружается.Если это действие не загружается, попробуйте обновить страницу в браузере. Также для этой страницы требуется javascript. Посетите сайт с помощью браузера с включенным JavaScript.

Если загрузка не удалась, нажмите здесь, чтобы повторить попытку.

Поздравляем — вы завершили Stack and Queue MCQ . Вы набрали %% SCORE %% из %% TOTAL %%. Ваша работа была оценена как %% RATING %%

. Ваши ответы выделены ниже.

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

Необходимо ответить на 8 вопросов.

Видеоурок по программированию в стеке.

Ссылка

Очереди и стеки — CPN Tools

Часто бывает приятно иметь возможность моделировать дисциплину очереди или стека для мест, например для связи по каналу TCP.

Увы, CPN Tools в настоящее время не поддерживает это, но разработчик моделей легко это делает.

Пример

Это очень простая модель отправителя и получателя.

Отправитель отправляет пакеты в сеть.

Приемник принимает пакеты из сети.

Стек

Мы хотим, чтобы сеть имела LIFO (последний пришел, первый вышел) или поведение стека. (Да, это нереально, но тогда мне нужно представить только один пример).

Мы меняем тип места с T на list T и делаем все входящие дуги перед списком, а все исходящие дуги должны затем удалить голову из списка.

Когда я делаю это с приведенным выше примером, я получаю:

Изменения в декларации

• Я добавил новый тип ПАКЕТЫ типа список ПАКЕТ
• Я добавил новую переменную нового типа ПАКЕТЫ

Изменения в сетевом месте

• Я меняю тип с ПАКЕТ на ПАКЕТОВ
• Я добавляю / изменяю начальную разметку на список. В этом случае исходной начальной маркировкой была пустая маркировка, и я добавляю пустой список [] .Если бы исходная маркировка была, например, 1`1 ++ 2`4 , я мог бы изменить ее, например, на [1,4,1] (порядок теперь имеет значение).

Изменения в дугах (входящих и исходящих)

• Меняю надпись дуги с p на p :: ps , где ps — новая переменная нового типа PACKAGEs
• Добавляю новую дугу в обратном направлении с надписью ps

Очереди

Мы хотим, чтобы сеть имела FIFO (первый пришел — первый ушел) или поведение очереди. Это похоже на поведение TCP-потоков.

Мы меняем тип места с T на list T и заставляем все входящие дуги добавляться в список, а все исходящие дуги должны затем удалять голову из списка.

Единственное отличие от стеков состоит в том, что мы не добавляем в начало списка, а добавляем его. Когда я проделываю это с примером, я получаю:

Изменения в декларации

• Я добавил новый тип ПАКЕТЫ типа список ПАКЕТ
• Я добавил новую переменную нового типа ПАКЕТЫ

Изменения в сетевом месте

• Я меняю тип с ПАКЕТ на ПАКЕТОВ
• Я добавляю / изменяю начальную разметку на список.В этом случае исходной начальной маркировкой была пустая маркировка, и я добавляю пустой список [] . Если бы исходная маркировка была, например, 1`1 ++ 2`4 , я мог бы изменить ее, например, на [1, 4, 1] (порядок теперь ДЕЙСТВИТЕЛЬНО имеет значение). [p] , где ps — новая переменная нового типа ПАКЕТЫ
• Добавляю новую дугу в обратном направлении с надписью ps

Приоритетные очереди

Мы хотим, чтобы сеть имела поведение очереди приоритетов, т.е.е. приоритет пакета определяет порядок, в котором он обрабатывается. Это похоже на параметры качества обслуживания IP, которые позволяют идентифицировать (и, возможно, обрабатывать) дейтаграммы с восемью уровнями приоритета.

Мы меняем тип места с T на list T , и заставляем все входящие дуги вставлять элементы в список в соответствии с приоритетом / приоритетом, и все исходящие дуги должны затем удалить голову из списка.

Отличие от очередей FIFO заключается в том, что вместо добавления в список элементы добавляются в соответствии с их приоритетом.Когда я проделываю это с примером, я получаю:

Изменения в декларации

• Я добавил новый тип ПАКЕТЫ типа список ПАКЕТ
• Я добавил новую переменную нового типа ПАКЕТЫ
• Я добавляю функцию superiorPriority , чтобы определить, имеет ли один пакет более высокий приоритет, чем другой
• Добавляю функцию pinsert для вставки пакетов в список по их приоритету

Изменения в сетевом месте

• Я меняю тип с ПАКЕТ на ПАКЕТОВ
• Я добавляю / изменяю начальную разметку на список. В этом случае исходной начальной маркировкой была пустая маркировка, и я добавляю пустой список [] . Если бы исходная маркировка была, например, 1`1 ++ 2`4 , я мог бы изменить ее, например, на [4, 1, 1] (порядок теперь ДЕЙСТВИТЕЛЬНО имеет значение).

Изменения исходящих дуг

• Меняю надпись дуги с p на p :: ps , где ps — новая переменная нового типа PACKAGEs
• Добавляю новую дугу в обратном направлении с надписью ps

Изменения входящей дуги

• Меняю надпись дуги с p на pinsert p ps , где ps — новая переменная нового типа PACKAGEs
• Добавляю новую дугу в обратном направлении с надписью ps

Примеры

Примеры, описанные в этом документе, можно скачать

Реализация очереди с использованием стека

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

• Делая операцию постановки в очередь (вставку) дорогостоящей.
• Делая операцию удаления из очереди дорогостоящей.

Очередь, использующая стеки, делая операцию постановки в очередь дорогостоящей

Реализация очереди с использованием стеков, делая операцию постановки в очередь дорогостоящей, обсуждается ниже.

1. Инициализировать stack1 и stack2, установив top1 = top2 = -1 .
2. Чтобы выполнить операцию постановки в очередь,

• Переместите все элементы из стека1 в стек2.
• Вставьте новый элемент в stack2.
• Вытолкнуть все элементы из стека 2 в стек 1.

3. Чтобы выполнить операцию удаления из очереди,

• Извлечь и вернуть элемент из стека1.

Программа C для реализации очереди с использованием стеков, делая операцию постановки в очередь дорогостоящей

Выход

1. ENQUEUE
2. ДЕКАБРЬ
3. ДИСПЛЕЙ
4. ВЫХОД

Введите свой выбор: 1
Введите данные: 15

Введите свой выбор: 1
Введите данные: 30

Введите свой выбор: 1
Введите данные: 45

Введите свой выбор: 3

ЭЛЕМЕНТЫ ОЧЕРЕДИ: 15 30 45

Введите ваш выбор: 2

Введите ваш выбор: 3

ЭЛЕМЕНТЫ ОЧЕРЕДИ: 30 45

Введите ваш выбор: 1
Введите данные: 60

Введите ваш выбор: 3

ОЧЕРЕДЬ ЭЛЕМЕНТЫ: 30 45 60

Введите свой выбор: 4

Очередь с использованием стеков, делая операцию удаления из очереди дорогостоящей

Реализация очереди с использованием стеков, делая операцию удаления из очереди дорогостоящей, обсуждается ниже.

1. Инициализировать stack1 и stack2, установив top1 = top2 = -1.
2. Чтобы выполнить операцию постановки в очередь,

• Нажмите на элемент, который нужно добавить в stack1.

3. Чтобы выполнить операцию удаления из очереди,

• Переместите все элементы из стека1 в стек2.
• Извлечь и вернуть элемент из стека 2.

Программа C для реализации очереди с использованием стеков, делая операцию удаления из очереди дорогостоящей

Если у вас есть отзывы об этом
статью и хотите улучшить ее, напишите на запрос @ faceprep.в

Очередь в сетевом стеке Linux — Дэн Симон

[Немного более короткая и отредактированная версия этой статьи появилась в июльском выпуске Linux Journal за 2013 год. Благодаря великолепной политике Linux Journal в отношении авторских прав мне все еще разрешено публиковать это на моем сайте. Перейдите сюда, чтобы подписаться на Linux Journal.]

Очереди пакетов являются основным компонентом любого сетевого стека или устройства. Они позволяют асинхронным модулям обмениваться данными, повышать производительность и иметь побочный эффект, влияющий на задержку.Эта статья призвана объяснить, где IP-пакеты помещаются в очередь в сетевом стеке Linux, как работают интересные новые функции уменьшения задержки, такие как BQL, и как управлять буферизацией для уменьшения задержки.

На приведенный ниже рисунок будут ссылаться повсюду, а модифицированные версии представлены для иллюстрации конкретных концепций.

Рисунок 1 — Упрощенный высокоуровневый обзор очередей на пути передачи сетевого стека Linux

Между стеком IP и контроллером сетевого интерфейса (NIC) находится очередь драйверов.Эта очередь обычно реализуется как кольцевой буфер «первым пришел — первым обслужен» (FIFO) — просто подумайте о нем как о буфере фиксированного размера. Очередь драйвера не содержит пакетных данных. Вместо этого он состоит из дескрипторов, которые указывают на другие структуры данных, называемые буферами ядра сокетов (SKB), которые содержат данные пакета и используются во всем ядре.

Рисунок 2 — Частично заполненная очередь драйвера с дескрипторами, указывающими на SKB

Источником ввода для очереди драйвера является IP-стек, который ставит в очередь полные IP-пакеты.Пакеты могут быть сгенерированы локально или получены на одной сетевой карте для маршрутизации на другую, когда устройство функционирует как IP-маршрутизатор. Пакеты, добавленные в очередь драйвера стеком IP, удаляются из очереди драйвером оборудования и отправляются по шине данных на оборудование NIC для передачи.

Причина, по которой существует очередь драйверов, состоит в том, чтобы гарантировать, что всякий раз, когда в системе есть данные для передачи, данные доступны для NIC для немедленной передачи. То есть очередь драйверов дает стеку IP место для асинхронной постановки в очередь данных в зависимости от работы оборудования.Один из альтернативных вариантов заключается в том, чтобы сетевая карта запрашивала данные у IP-стека, когда физический носитель готов к передаче. Поскольку ответ на этот запрос не может быть мгновенным, такая конструкция упускает ценные возможности передачи, что приводит к снижению пропускной способности. Противоположный подход состоит в том, чтобы стек IP ждал после создания пакета, пока оборудование не будет готово к передаче. Это также не идеально, потому что стек IP не может перейти к другой работе.

Огромные пакеты из стека

Большинство сетевых карт имеют фиксированную максимальную единицу передачи (MTU), которая является самым большим кадром, который может быть передан с помощью физической среды.Для Ethernet значение MTU по умолчанию составляет 1500 байтов, но некоторые сети Ethernet поддерживают Jumbo-кадры размером до 9000 байтов. Внутри сетевого стека IP MTU может проявляться как ограничение на размер пакетов, отправляемых на устройство для передачи. Например, если приложение записывает 2000 байтов в сокет TCP, тогда стеку IP необходимо создать два IP-пакета, чтобы размер пакета был меньше или равен 1500 MTU. При передаче больших объемов данных сравнительно небольшой MTU вызывает создание большого количества небольших пакетов и их передачу через очередь драйверов.

Чтобы избежать накладных расходов, связанных с большим количеством пакетов на пути передачи, в ядре Linux реализовано несколько оптимизаций: разгрузка сегментации TCP (TSO), разгрузка фрагментации UDP (UFO) и разгрузка общей сегментации (GSO). Все эти оптимизации позволяют стеку IP создавать пакеты, размер которых превышает MTU исходящей сетевой карты. Для IPv4 пакеты размером не более 65 536 байт могут быть созданы и помещены в очередь драйвера. В случае TSO и UFO оборудование NIC берет на себя ответственность за разбиение одного большого пакета на пакеты, достаточно маленькие для передачи по физическому интерфейсу.Для сетевых адаптеров без аппаратной поддержки GSO выполняет ту же операцию в программном обеспечении непосредственно перед постановкой в ​​очередь драйвера.

Напомним ранее, что очередь драйверов содержит фиксированное количество дескрипторов, каждый из которых указывает на пакеты различного размера. Поскольку TSO, UFO и GSO допускают гораздо большие пакеты, эти оптимизации имеют побочный эффект значительного увеличения количества байтов, которые могут быть поставлен в очередь водителя. Рисунок 3 иллюстрирует эту концепцию в отличие от рисунка 2.

Рисунок 3 — Большие пакеты могут быть отправлены на NIC, когда включены TSO, UFO или GSO. Это может значительно увеличить количество байтов в очереди драйвера.

В то время как остальная часть этой статьи посвящена пути передачи, стоит отметить, что в Linux также есть оптимизации на стороне приема, которые работают аналогично TSO, UFO и GSO. Эти оптимизации также имеют цель снизить накладные расходы на каждый пакет. В частности, общая разгрузка приема (GRO) позволяет драйверу сетевого адаптера объединять полученные пакеты в один большой пакет, который затем передается в стек IP.При пересылке пакетов GRO позволяет восстанавливать исходные пакеты, что необходимо для поддержания сквозного характера IP-пакетов. Однако есть один побочный эффект: когда большой пакет разбивается на передающей стороне операции пересылки, это приводит к тому, что сразу несколько пакетов для потока помещаются в очередь. Этот «микропакет» пакетов может отрицательно повлиять на задержки между потоками.

Голодание и задержка

Несмотря на необходимость и преимущества, очередь между стеком IP и оборудованием создает две проблемы: голодание и задержку.

Если драйвер сетевой карты просыпается, чтобы вытащить пакеты из очереди на передачу, а очередь пуста, оборудование упускает возможность передачи, тем самым снижая пропускную способность системы. Это называется голоданием. Обратите внимание, что пустая очередь, когда системе нечего передавать, не является голоданием — это нормально. Сложность, связанная с предотвращением голодания, заключается в том, что IP-стек, заполняющий очередь, и драйвер оборудования, опорожняющий очередь, работают асинхронно.Хуже того, продолжительность между событиями заполнения или слива зависит от нагрузки на систему и внешних условий, таких как физическая среда сетевого интерфейса. Например, в загруженной системе IP-стек получит меньше возможностей для добавления пакетов в буфер, что увеличивает шансы того, что оборудование опустошит буфер до того, как в очередь будет поставлено больше пакетов. По этой причине желательно иметь очень большой буфер, чтобы снизить вероятность голода и обеспечить высокую пропускную способность.

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

Рисунок 4 — Интерактивный пакет (желтый) за пакетами массового потока (синий)

На рисунке 4 показана очередь драйвера, которая почти заполнена сегментами TCP для одного потока массового трафика с высокой пропускной способностью (синий). Последний в очереди — это пакет от VoIP или игрового потока (желтый). Интерактивные приложения, такие как VoIP или игры, обычно излучают небольшие пакеты с фиксированными интервалами, которые чувствительны к задержке, в то время как передача данных с высокой пропускной способностью генерирует более высокую скорость пакетов и более крупные пакеты. Эта более высокая скорость передачи пакетов может заполнять буфер между интерактивными пакетами, вызывая задержку передачи интерактивного пакета. Чтобы проиллюстрировать это поведение, рассмотрим сценарий, основанный на следующих предположениях:

• Сетевой интерфейс, способный передавать со скоростью 5 Мбит / сек или 5 000 000 бит / сек.
• Размер каждого пакета из массового потока составляет 1500 байтов или 12000 бит.
• Размер каждого пакета из интерактивного потока составляет 500 байтов.
• Глубина очереди — 128 дескрипторов
• Последним в очереди находится 127 пакетов данных и 1 интерактивный пакет.

С учетом приведенных выше предположений время, необходимое для слива 127 массовых пакетов и создания возможности передачи для интерактивного пакета, составляет (127 * 12 000) / 5 000 000 = 0.304 секунды (304 миллисекунды для тех, кто думает о задержке с точки зрения результатов пинга). Эта величина задержки намного превышает допустимую для интерактивных приложений, и это даже не представляет собой полное время приема-передачи — это всего лишь время, необходимое для передачи пакетов, поставленных в очередь перед интерактивным. Как описано ранее, размер пакетов в очереди драйвера может превышать 1500 байт, если включены TSO, UFO или GSO. Соответственно, это усугубляет проблему задержки.

Большие задержки, вызываемые неуправляемыми буферами слишком большого размера, известны как Bufferbloat. Для более подробного объяснения этого явления см. Управление задержкой очереди и проект Bufferbloat.

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

Пределы очереди байтов (BQL)

Byte Queue Limits (BQL) — это новая функция в последних ядрах Linux (> 3.3.0), который пытается автоматически решить проблему определения размера очереди драйверов. Это достигается путем добавления уровня, который включает и отключает формирование очереди в очередь драйвера на основе расчета минимального размера буфера, необходимого для предотвращения зависания в текущих условиях системы. Напомним, что чем меньше объем данных в очереди, тем меньше максимальная задержка для пакетов в очереди.

Важно понимать, что фактический размер очереди драйверов не изменяется BQL.Скорее BQL вычисляет предел количества данных (в байтах), которые могут быть поставлены в очередь в текущий момент. Любые байты, превышающие этот предел, должны удерживаться или отбрасываться уровнями выше очереди драйвера.

Механизм BQL работает, когда происходят два события: когда пакеты помещаются в очередь драйвера и когда передача по сети завершена. Упрощенная версия алгоритма BQL представлена ​​ниже. LIMIT относится к значению, рассчитанному BQL.

 ****
** После добавления пакетов в очередь
****

если количество байтов в очереди превышает текущее значение LIMIT, тогда
        отключить очередь дополнительных данных в очередь драйвера 

Обратите внимание, что объем данных в очереди может превышать LIMIT, поскольку данные помещаются в очередь до выполнения проверки LIMIT. Поскольку большое количество байтов может быть поставлено в очередь за одну операцию, когда включены TSO, UFO или GSO, эти оптимизации пропускной способности имеют побочный эффект, позволяя ставить в очередь больший, чем желательный, объем данных. Если вам важна задержка, вы, вероятно, захотите отключить эти функции. См. Дальнейшие части этой статьи, чтобы узнать, как это сделать.

Второй этап BQL выполняется после того, как оборудование завершило передачу (упрощенный псевдокод):

 ****
** Когда оборудование завершило отправку пакета пакетов
** (обозначается как конец интервала)
****

если в интервале не хватало оборудования
        увеличить LIMIT

иначе, если оборудование было занято в течение всего интервала (не голодало) и есть байты для передачи
        уменьшить LIMIT на количество байтов, не переданных в интервале

если количество байтов в очереди меньше LIMIT
        включить очередь дополнительных данных в буфер 

Как видите, BQL основан на проверке того, было ли устройство на голодном питании. Если он был голоден, то LIMIT увеличивается, позволяя поставить в очередь больше данных, что снижает вероятность голодания. Если устройство было занято в течение всего интервала и в очереди еще есть байты, которые нужно передать, то очередь больше, чем необходимо для системы в текущих условиях, и LIMIT уменьшается, чтобы ограничить задержку.

Реальный пример может помочь понять, насколько BQL влияет на объем данных, которые могут быть поставлены в очередь. На одном из моих серверов размер очереди драйверов по умолчанию равен 256 дескрипторам.Поскольку Ethernet MTU составляет 1500 байт, это означает, что до 256 * 1500 = 384 000 байт могут быть поставлены в очередь драйвера (TSO, GSO и ​​т. Д. Отключены или это будет намного больше). Однако предельное значение, рассчитанное BQL, составляет 3012 байт. Как видите, BQL сильно ограничивает объем данных, которые можно поставить в очередь.

Об интересном аспекте BQL можно судить по первому слову в имени — байту. В отличие от размера очереди драйверов и большинства других очередей пакетов, BQL работает с байтами. Это связано с тем, что количество байтов имеет более прямую связь со временем, требуемым для передачи на физический носитель, чем количество пакетов или дескрипторов, поскольку последние имеют переменный размер.

BQL сокращает задержку в сети, ограничивая объем данных в очереди до минимума, необходимого для предотвращения зависания. Это также имеет очень важный побочный эффект — перемещение точки, в которой большинство пакетов ставится в очередь, из очереди драйвера, которая представляет собой простой FIFO, на уровень дисциплины очередей (QDisc), который способен реализовывать гораздо более сложные стратегии организации очереди.В следующем разделе представлен уровень Linux QDisc.

Очередь драйверов — это простая очередь «первым пришел — первым ушел» (FIFO). Он обрабатывает все пакеты одинаково и не имеет возможности различать пакеты разных потоков. Такая конструкция обеспечивает простоту и скорость программного обеспечения драйвера сетевой карты. Обратите внимание, что более продвинутый Ethernet и большинство беспроводных сетевых адаптеров поддерживают несколько независимых очередей передачи, но аналогично каждая из этих очередей обычно является FIFO. Более высокий уровень отвечает за выбор того, какую очередь передачи использовать.

Между стеком IP и очередью драйверов находится уровень дисциплины очередей (QDisc) (см. Рисунок 1). Этот уровень реализует возможности управления трафиком ядра Linux, которые включают классификацию трафика, приоритизацию и формирование скорости. Уровень QDisc настраивается с помощью несколько непрозрачной команды tc. На уровне QDisc необходимо понимать три ключевых понятия: QDisc, классы и фильтры.

QDisc — это абстракция Linux для очередей трафика, которые более сложны, чем стандартная очередь FIFO.Этот интерфейс позволяет QDisc выполнять сложные операции управления очередью, не требуя изменения стека IP или драйвера сетевой карты. По умолчанию каждому сетевому интерфейсу назначается pfifo_fast QDisc, который реализует простую трехполосную схему приоритизации на основе битов TOS. Несмотря на то, что он используется по умолчанию, pfifo_fast QDisc — далеко не лучший выбор, потому что по умолчанию он имеет очень глубокие очереди (см. Txqueuelen ниже) и не поддерживает поток.

Вторая концепция, которая тесно связана с QDisc, — это класс.Отдельные QDisc могут реализовывать классы, чтобы по-разному обрабатывать подмножества трафика. Например, QDisc Hierarchical Token Bucket (HTB) позволяет пользователю настраивать классы 500 Кбит / с и 300 Кбит / с и направлять трафик к каждому по желанию. Не все QDisc поддерживают несколько классов — те, которые поддерживают, называются классовыми QDisc.

Фильтры (также называемые классификаторами) — это механизм, используемый для классификации трафика для определенного QDisc или класса. Есть много разных типов фильтров разной сложности.u32 является наиболее общим и, пожалуй, самым простым в использовании фильтром потока. Документация по фильтру потока отсутствует, но вы можете найти пример в одном из моих сценариев QoS.

Для получения более подробной информации о QDiscs, классах и фильтрах см. LARTC HOWTO и справочные страницы tc.

Глядя на предыдущие рисунки, вы могли заметить, что над уровнем дисциплины очередей нет очередей пакетов. Это означает, что сетевой стек помещает пакеты непосредственно в дисциплину организации очередей или отодвигает обратно на верхние уровни (например, буфер сокета), если очередь заполнена.Возникает очевидный вопрос: что происходит, когда в стеке много данных для отправки? Это могло произойти в результате TCP-соединения с большим окном перегрузки или, что еще хуже, приложения, отправляющего UDP-пакеты с максимальной скоростью. Ответ заключается в том, что для QDisc с единственной очередью возникает та же проблема, что и для очереди драйверов, показанная на рисунке 4. То есть один поток с высокой пропускной способностью или высокой скоростью передачи пакетов может занимать все пространство в очереди, вызывая потерю пакетов и добавляя значительную задержку для других потоков.Хуже того, это создает еще одну точку буферизации, в которой может образоваться постоянная очередь, что увеличивает задержку и вызывает проблемы при расчетах RTT TCP и размера окна перегрузки. Поскольку в Linux по умолчанию используется pfifo_fast QDisc, который фактически имеет единственную очередь (поскольку большая часть трафика помечена как TOS = 0), это явление не редкость.

Начиная с Linux 3.6.0 (30.09.2012), ядро ​​Linux имеет новую функцию под названием TCP Small Queues, которая направлена ​​на решение этой проблемы для TCP. Небольшие очереди TCP добавляют ограничение для каждого потока TCP на количество байтов, которые могут быть поставлены в очередь в QDisc и очереди драйверов в любой момент времени.Это имеет интересный побочный эффект, заставляющий ядро ​​отодвигать приложение раньше, что позволяет приложению более эффективно определять приоритеты записи в сокет. В настоящее время (2012-12-28) все еще возможно, чтобы отдельные потоки от других транспортных протоколов переполняли уровень QDisc.

Другое частичное решение проблемы лавинной рассылки транспортного уровня, которое не зависит от транспортного уровня, состоит в использовании QDisc, который имеет много очередей, в идеале по одной на сетевой поток. И стохастическая организация очередей (SFQ), и справедливая организация очередей с контролируемой задержкой (fq_codel) QDiscs хорошо подходят для решения этой проблемы, поскольку они эффективно имеют очередь на сетевой поток.

Очередь драйверов

Команда ethtool используется для управления размером очереди драйверов для устройств Ethernet. ethtool также предоставляет низкоуровневую статистику интерфейса, а также возможность включать и отключать IP-стек и функции драйверов.

Флаг -g для ethtool отображает параметры очереди (звонка) драйвера:

 [root @ alpha net-next] # ethtool -g eth0
Параметры звонка для eth0:
Предустановленные максимумы:
RX: 16384
RX Mini: 0
RX Jumbo: 0
Техас: 16384
Текущие настройки оборудования:
RX: 512
RX Mini: 0
RX Jumbo: 0
Техас: 256 

Из вышеприведенного вывода видно, что драйвер для этой сетевой карты по умолчанию использует 256 дескрипторов в очереди передачи.В начале исследования Bufferbloat часто рекомендовали уменьшить размер очереди драйверов, чтобы уменьшить задержку. С введением BQL (при условии, что ваш драйвер сетевой карты его поддерживает) больше нет причин изменять размер очереди драйвера (см. Ниже, как настроить BQL).

Ethtool также позволяет управлять функциями оптимизации, такими как TSO, UFO и GSO. Флаг -k отображает текущие настройки разгрузки, а -K изменяет их.

 [dan @ alpha ~] $ ethtool -k eth0
Параметры разгрузки для eth0:
rx-контрольная сумма: выкл.
tx-контрольная сумма: выкл.
разброс-сборка: выкл.
tcp-segmentation-offload: выключено
udp-фрагментация-разгрузка: выключено
generic-segmentation-offload: выключено
общий-получение-разгрузка: на
большой прием-разгрузка: выкл.
rx-vlan-offload: выключено
tx-vlan-offload: выключено
ntuple-filters: выключено
получение-хеширование: выкл. 

Поскольку TSO, GSO, UFO и GRO значительно увеличивают количество байтов, которые могут быть поставлены в очередь драйвера, вам следует отключить эти оптимизации, если вы хотите оптимизировать задержку по сравнению с пропускной способностью.Сомнительно, что вы заметите какое-либо влияние на ЦП или снижение пропускной способности при отключении этих функций, если только система не обрабатывает очень высокие скорости передачи данных.

Пределы очереди байтов (BQL)

Алгоритм BQL является самонастраивающимся, так что вам, вероятно, не придется слишком сильно с ним связываться. Однако, если вас беспокоят оптимальные задержки при низких скоростях передачи данных, вам может потребоваться переопределить верхний предел вычисленного значения LIMIT. Состояние и конфигурацию BQL можно найти в каталоге / sys в зависимости от расположения и имени сетевой карты.На моем сервере каталог для eth0:

 /sys/devices/pci0000:00/0000:00:14.0/net/eth0/queues/tx-0/byte_queue_limits 

В этом каталоге находятся следующие файлы:

• hold_time: время между изменением LIMIT в миллисекундах.
• в полете: количество байтов в очереди, но еще не переданных.

Предел

• : ПРЕДЕЛЕННОЕ значение, рассчитанное BQL. 0, если BQL не поддерживается драйвером сетевой карты.
• limit_max: настраиваемое максимальное значение для LIMIT. Установите это значение ниже, чтобы оптимизировать задержку.
• limit_min: настраиваемое минимальное значение для LIMIT. Установите это значение выше, чтобы оптимизировать пропускную способность.

Чтобы установить жесткий верхний предел количества байтов, которые могут быть поставлены в очередь, запишите новое значение в limit_max fie.

 эхо "3000"> limit_max 

Что такое txqueuelen?

Часто в ранних обсуждениях Bufferbloat упоминалась идея статического сокращения очереди передачи NIC. Текущий размер очереди передачи можно узнать с помощью команд ip и ifconfig.Как ни странно, эти команды по-разному называют длину очереди передачи (жирный текст):

 [дан @ alpha ~] $ ifconfig eth0
eth0 Link encap: Ethernet HWaddr 00: 18: F3: 51: 44: 10
inet адрес: 69.41.199.58 Bcast: 69.41.199.63 Маска: 255.255.255.248
inet6 адрес: fe80 :: 218: f3ff: fe51: 4410/64 Объем: Ссылка
ВВЕРХ ТРАНСЛЯЦИИ МУЛЬТИКАСТ MTU: 1500 Метрика: 1
Пакеты RX: 435033 ошибок: 0 отброшено: 0 переполнений: 0 кадров: 0
Пакеты TX: 429919 ошибок: 0 сброшено: 0 переполнений: 0 носитель: 0
коллизии: 0  txqueuelen: 1000 
Байт RX: 65651219 (62.6 МБ) Байт TX: 132143593 (126,0 МБ)
Прерывание: 23 

 [dan @ alpha ~] $ ip ссылка
1: lo: mtu 16436 qdisc noqueue state UNKNOWN
ссылка / петля 00: 00: 00: 00: 00: 00 brd 00: 00: 00: 00: 00: 00
2: eth0: mtu 1500 qdisc pfifo_fast state UP  qlen 1000 
ссылка / эфир 00: 18: f3: 51: 44: 10 brd ff: ff: ff: ff: ff: ff 

Длина очереди передачи в Linux по умолчанию составляет 1000 пакетов, что представляет собой большой объем буферизации, особенно при низкой пропускной способности.

Интересный вопрос: что именно контролирует эта переменная? Для меня это было непонятно, поэтому я потратил некоторое время на изучение исходного кода ядра. Насколько я могу судить, txqueuelen используется только как длина очереди по умолчанию для или дисциплин очередей. В частности:

• pfifo_fast (дисциплина очереди по умолчанию в Linux)
• sch_fifo
• sch_gred
• sch_htb (только для очереди по умолчанию)
• штепсельная розетка
• sch_sfb
• sch_teql

Если вернуться к рисунку 1, то параметр txqueuelen управляет размером очередей в поле Queuing Discipline для перечисленных выше QDiscs.Для большинства этих дисциплин организации очередей аргумент «limit» в командной строке tc отменяет значение по умолчанию для txqueuelen. Таким образом, если вы не используете одну из вышеперечисленных дисциплин организации очереди или если вы переопределяете длину очереди, значение txqueuelen не имеет смысла.

Кстати, меня немного сбивает с толку то, что команда ifconfig показывает подробности низкого уровня сетевого интерфейса, такие как MAC-адрес, но параметр txqueuelen относится к более высокоуровневому уровню QDisc. Кажется более подходящим для этого ifconfig показывал бы размер очереди драйвера.

Длина очереди передачи настраивается с помощью команд ip или ifconfig.

 [root @ alpha dan] # набор IP-ссылок txqueuelen 500 dev eth0 

Обратите внимание, что в команде ip используется «txqueuelen», но при отображении деталей интерфейса используется «qlen» — еще одно досадное несоответствие.

Дисциплины очередности

Как было сказано ранее, ядро ​​Linux имеет большое количество дисциплин организации очередей (QDiscs), каждая из которых реализует свои собственные очереди пакетов и поведение.Описание деталей того, как настроить каждый из QDiscs, выходит за рамки данной статьи. Для получения полной информации см. Справочную страницу tc (man tc). Подробную информацию о каждом QDisc можно найти в «man tc qdisc-name» (например, «man tc htb» или «man tc fq_codel»). LARTC также является очень полезным ресурсом, но в нем отсутствует информация о новых функциях.

Ниже приведены несколько полезных советов и приемов, связанных с командой tc:

• HTB QDisc реализует очередь по умолчанию, которая принимает все пакеты, если они не классифицированы правилами фильтрации.Некоторые другие QDiscs, такие как DRR, просто неклассифицированный трафик черной дыры. Чтобы узнать, сколько пакетов было неправильно классифицировано и было напрямую поставлено в очередь в класс HTB по умолчанию, см. Direct_packets_stat в «tc qdisc show».
• Иерархия классов HTB полезна только для классификации, но не для распределения полосы пропускания. Распределение всей полосы пропускания происходит путем просмотра листьев и связанных с ними приоритетов.
• Инфраструктура QDisc идентифицирует QDiscs и классы со старшими и младшими номерами, разделенными двоеточием.Старший номер — это идентификатор QDisc, а младший номер — класс в этом QDisc. Загвоздка в том, что команда tc использует шестнадцатеричное представление этих чисел в командной строке. Поскольку многие строки действительны как в шестнадцатеричном, так и в десятичном формате (например, 10), многие пользователи даже не осознают, что tc использует шестнадцатеричный формат. Посмотрите один из моих сценариев tc, чтобы узнать, как я с этим справляюсь.
• Если вы используете ADSL, который является ATM (большинство услуг DSL основаны на ATM, но более новые варианты, такие как VDSL2, не всегда), вы, вероятно, захотите добавить опцию «linklayer adsl».Это объясняет накладные расходы, возникающие при разбиении IP-пакетов на группу 53-байтовых ячеек ATM.
• Если вы используете PPPoE, вы, вероятно, захотите учесть накладные расходы PPPoE с помощью параметра «overhead».

Ограничение очереди TCP на сокет можно просмотреть и контролировать с помощью следующего файла / proc:

 / proc / sys / net / ipv4 / tcp_limit_output_bytes 

Я понимаю, что вам не нужно изменять это значение в любой нормальной ситуации.

К сожалению, не все очереди большого размера, которые влияют на производительность вашего Интернета, находятся под вашим контролем. Чаще всего проблема заключается в устройстве, которое подключено к вашему поставщику услуг (например, DSL или кабельный модем), или в самом оборудовании поставщика услуг. В последнем случае вы мало что можете сделать, потому что нет способа контролировать трафик, который направляется к вам. Однако в восходящем направлении вы можете формировать трафик так, чтобы он был немного ниже скорости соединения.Это предотвратит то, что очередь в устройстве никогда не будет иметь более пары пакетов. Многие домашние домашние маршрутизаторы имеют настройку ограничения скорости, которую можно использовать для изменения скорости соединения ниже скорости соединения. Если вы используете Linux-сервер в качестве маршрутизатора, формирование ниже скорости канала также позволяет эффективно использовать функции очереди ядра. Вы можете найти много примеров сценариев tc в Интернете, в том числе тот, который я использую с некоторыми связанными результатами производительности.

Организация очередей в буферах пакетов — необходимый компонент любой сети с коммутацией пакетов как внутри устройства, так и между элементами сети.Правильное управление размером этих буферов имеет решающее значение для достижения хорошей задержки в сети, особенно под нагрузкой. Хотя статический размер буфера может сыграть роль в уменьшении задержки, реальным решением является интеллектуальное управление объемом данных в очереди. Это лучше всего достигается с помощью динамических схем, таких как BQL, и методов активного управления очередью (AQM), таких как Codel. В этой статье описано, где пакеты помещаются в очередь в сетевом стеке Linux, как настраиваются функции, связанные с очередями, и даны некоторые рекомендации о том, как достичь низкой задержки.