Как называется бесконечная работа алгоритма
Алгоритмы, которые работают бесконечно
У каждого десятилетия свои увлекательные головоломки; и если в начале 1980-х годов бесспорное первое место среди математических развлечений занимал кубик Рубика, то «Тетрис» вызывает похожее чувство ностальгии по концу 80-х и началу 90-х годов.
У кубика Рубика и «Тетриса» есть кое-что общее: математический оттенок, базирующийся на стилизованных геометрических формах, — но пожалуй, различия между ними представляют еще больший интерес.
Эти отличительные признаки «Тетриса» напоминают аналогичные темы, про- явившиеся в недавних работах по анализу алгоритмов. Все чаще встречаются ситуации, в которых традиционные представления об алгоритмах — в начале выполнения алгоритм получает входные данные, выполняется за конечное количество шагов и выдает результат — уже неприменимы.
Попробуйте представить себе маршрутизаторы в Интернете, которые передают пакеты и пытаются избежать перегрузок; или децентрализованные механизмы обмена файлами, которые копируют и распространяют контент по требованию пользователей; или средства машинного обучения, формирующие прогностические модели концепций, изменяющихся со временем; во всех этих случаях мы имеем дело с алгоритмами, практически предназначенными для бесконечного выполнения.
Признаком успешного выполнения является не окончательный результат, а способность алгоритма сохранить работоспособность в постоянно изменяющейся среде, постоянно подкидывающей новые задачи. В таких ситуациях мы переходим из мира кубика Рубика в мир «Тетриса».
Существует много разных примеров, на которых можно исследовать эту тему. В последнем разделе книги мы рассмотрим одну из самых интересных ситуаций: разработку алгоритмов для высокоскоростной коммутации пакетов в Интернете.
Кто же ты такой, алгоритм?
Сегодня довольно легко столкнуться с недобросовестными школьными учебниками, в частности с учебниками по информатике. В главах, посвященных алгоритмам, вы можете найти непосредственно определение алгоритма. Не пояснение, о чем идет речь, не рассказ о предмете, а именно определение. Причем выделенное жирным шрифтом, старательно обведенное в рамку и помеченное какой-нибудь заметной пиктограммой в виде восклицательного знака. Обычно приправлено всё это соусом из кучи обязательных и необязательных свойств, образуя в итоге феерический кавардак. Давайте попытаемся понять, что же такое алгоритм, почему мы не может дать ему конкретного определения и выясним, какие свойства являются обязательными, а какие нет.
Составителей учебников легко понять, ведь на самом деле строгого определения алгоритма не существует, и более того, такого определения быть не может. Но вместо попыток объяснить, что к чему, авторы подсовывают бедным ученикам еще одно задание по зубрежке бесполезных и неправильных терминов. Чтобы не быть голословным, приведу выдержку из одного весьма распространенного учебника:
В университетах дела обстоят получше, однако автору этих строк на курсе по математической логике и теории алгоритмов пришлось столкнуться все с тем же винегретом из определения алгоритма и его свойств. Разберемся, что тут не так.
Бесконечность не предел
Такой же трюк с нумерацией не пройдет для бесконечных непериодических дробей (иррациональных чисел). Допустим такое множество счетное, то есть элементы этого множества можно пронумеровать натуральными числами. Тогда рассмотрим бесконечную десятичную дробь с нулевой целой частью, у которой первая цифра после запятой не равняется цифре на той же позиции у дроби с номером 1, вторая цифра не равняется цифре на второй позиции у дроби с номером 2 и т.д. Тогда полученная дробь будет заведомо отличаться от всех дробей хотя бы одной цифрой. Получается для нее не нашлось номера в нашей бесконечной нумерации! Примененная схема доказательства называется канторовским диагональным методом в честь придумавшего ее математика Георга Кантора.
Про бесконечные дроби
Не стоит делать ошибку, записывая в иррациональные числа все бесконечные дроби. Иррациональными являются только те числа, которые нельзя представить в виде несократимой дроби вида m/n. В десятичной системе счисления дроби 1/3 и 2/7 тоже окажутся бесконечными, однако их «бесконечность« обусловлена выбранной системой счисления. В системе счисления по основанию 21 эти дроби будут иметь конечное представление, а вот, например, дробь 1/2 окажется бесконечной (периодической).
Говорят, что множество бесконечных десятичных дробей имеет мощность континуум, которая обозначается символом ℵ1 (алеф-один). В дальнейшем нам понадобится следующее множество. Рассмотрим некоторый алфавит (конечное множество символов). Теперь представим множество всех конечных цепочек символов алфавита A*. Коль скоро алфавит конечен, и каждая цепочка конечна, то множество таких цепочек счетно (их можно пронумеровать натуральными числами).
На сколько велика бесконечность?
Допустим в наш алфавит вошли все придуманные на земле символы: русский алфавит, японские иероглифы, шумерская клинопись и т.д. Тогда в наше множество войдут все написанные когда-либо книги, все книги, которые будут написаны и все книги, которые никто не стал бы писать (например, хаотичные последовательности символов). Кроме того, представим книгу, толщиной в Солнечную систему и диагональю листа равной диаметру Млечного Пути, набранную 12-м шрифтом. В наше придуманное множество войдут все такие книги, отличающиеся хотя бы одним символов, и не только они, ведь вселенная бесконечна! Кто мешает представить себе книгу, размером в миллиарды световых лет? А все такие книги? Уже на этом этапе воображение может давать сбои, а ведь наше множество всего лишь счетное. Чтобы дополнить множество до континуума, нужно рассмотреть бесконечную книгу, по сравнению с которой, предыдущие книги — детские игрушки. Но и одной бесконечной книги нам не хватит, нужно рассмотреть все бесконечные книги.
Конструктивно оперировать континуальными бесконечностями невозможно. Даже работая со счетными множествами, мы не рассматриваем сами множества, а только говорим, что какой бы не был элемент N, всегда найдется элемент N+1. Если мы ставим себе прикладную задачу, появление в наших рассуждениях континуальной бесконечности должно служить нам «тревожной лампочкой»: осторожно, выход за пределы конструктивного.
Алгоритмы и вычислимость
Компьютер проводит свои вычисления, подчиняясь некоторой программе, которая воплощает собой конструктивную процедуру, или алгоритм. Не сложно догадаться, что алгоритм как раз и есть то правило, по которому вычисляется функция. Можно сказать, функция считается вычислимой, если для нее существует некоторый алгоритм.
Понятия алгоритм и вычислимая функция оказываются настолько заковыристыми, что некоторые составители учебной литературы не утруждают себя попытками разъяснить их суть. Дело в том, что определения алгоритма не существует, и кроме того, существовать не может, иначе пришлось бы выбросить на свалку целый раздел математики — теорию вычислимости. Попробуем разобраться более подробнее.
Частично-рекурсивные функции и тезис Черча
Все началось с того, что математик Давид Гильберт в 1900 году предложил список нерешенных на тот момент математических проблем. Позже выяснилось, что десятая проблема (проблема решения произвольного диофантового уравнения) оказалось неразрешимой, но для доказательства этого факта пришлось составить целую новую математическую теорию. Вопросами того, какие задачи можно конструктивно решить, и что такое конструктивное решение, занялись математики Курт Гедель, Стивен Клини, Алонсо Черч и Алан Тьюринг.
Курт Гедель наиболее известен тем, что сформулировал и доказал 2 теоремы о неполноте. Между прочим, сделал он это в возрасте всего лишь 24 лет.
Как выяснилось выше, континуальные бесконечности не всегда подходят под конструктивные рассуждения, поэтому Гедель и Клини предложили рассматривать только функции натурального аргумента (при необходимости любые функции над счетными множествами можно привести к «натуральным функция» путем замены элементов множеств их номерами). Изучая вычислимость таких функций, Гедель, Клини, Аккерман и другие математики пришли к так называемому классу частично-рекурсивных функций. В качестве определения этого класса рассматривается набор базовых, очень простых функций (константа, увеличение на единицу и проекция, которая сопоставляет функции многих аргументов один из ее аргументов) и операторов, позволяющих из функций строить новые функции (операторы композиции, примитивной рекурсии и минимизации). Слово «частичные» показывает, что эти функции определены лишь на некоторых числах. На остальных они не могут быть вычислены. Попытки расширить класс частично-рекурсивных функций ни к чему не привели, так как введение новых операций приводило к тому, что получалось множество функций, совпадающее с классом частично-рекурсивных. В дальнейшем Алонсо Черч отказался от попыток расширения этого класса, заявив, что, видимо:
Частично-рекурсивные функции соответствуют вычислимым функциям в любом разумном понимании вычислимости.
Это утверждение называют тезисом Черча. Стоит отметить, что тезис Черча не является теоремой или доказанным утверждением. Во-первых, не понятно, что такое «разумное понимание», во-вторых, превратив тезис Черча в доказанный факт, мы лишаем себя перспектив дальнейшего исследования вычислимости и механизмов вычислений. Никто, впрочем, не мешает попробовать определить такой набор операций, который был бы мощнее базиса для частично-рекурсивных функций. Только вот, до сих пор это никому не удавалось сделать.
Ученые долго не могли привести пример частично-рекурсивной функции, не являющейся примитивно-рекурсивной (без оператора минимизации). Наконец это удалось Вильгельму Аккерману. Предложенная функция Аккермана растет так быстро, что количество цифр в десятичной записи числа A(4,4) превосходит количество атомов во Вселенной.
Формальная теория алгоритмов во многом построена аналогично теории вычислимости. Считается, что алгоритм есть некое конструктивное преобразование входного слова (цепочки символов некоторого алфавита) в некоторое выходное слово. Опять же, здесь мы имеем с функциями вида A*->A*. Конечно, предложенное описание не подходит под определение алгоритма, так как неясно, что же такое «конструктивное преобразование». Хоть понятия алгоритма и вычислимой функции близки, не стоит их смешивать. Для одного и того же алгоритма может быть предъявлено сколько угодно его записей на каком-нибудь формальном языке, но соответствующая вычислимая функция всегда одна. Один из основателей формальной теории алгоритмов, Алан Тьюринг, предложил формальную модель автомата, известного как машина Тьюринга. Тезис Тьюринга гласит:
Каково бы не было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.
Любые попытки построить более мощные автомат заканчивались неудачей: для каждого такого автомата (машина Поста, нормальные алгоритмы Маркова, автоматы с регистрами и несколькими лентами) удавалось построить аналогичную машину Тьюринга. Некоторые ученые объединяют тезис Черча и тезис Тьюринга в тезис Черча-Тьюринга, так как они весьма близки по духу.
С помощью такого незамысловатого автомата можно формализовать любой алгоритм.
Таким образом, определив понятие алгоритма, мы будем вынуждены забыть о тезисе Черча-Тьюринга, и отказаться от целой математической теории, богатой содержанием и подарившую нам множество практических результатов.
Свойства алгоритмов
Мы выяснили, почему у алгоритма не может быть конкретного определения. Однако можно определить свойства, которыми должен обладать каждый алгоритм. К сожалению, в литературе часто смешивают обязательные и необязательный свойств. Разберемся подробнее.
Обязательные свойства
Начнем с обязательных свойств. Алгоритм можно записать в виде конечного текста из символов конечного алфавита. Действительно, бесконечный текст мы не можем записать чисто технически, а раз алгоритмы имеют отношение к конструктивной деятельности, бесконечными они быть не могут. Возможность представить алгоритм в виде конечного текста можно назвать свойством объективности и конечности.
Еще одно достаточно очевидное свойство любого алгоритма — его дискретность. Независимо от исполнителя, исполнение алгоритма представляет собой дискретный процесс, при рассмотрение распадающийся на элементарные действия. Понимать дискретность можно и в том смысле, что любая информация, над которой работает алгоритм может быть представлена в виде текста.
Третье фундаментальное свойство алгоритмов называется детерминированностью. Оно заключается в том, что следовать предписанной процедуре можно только одним способом. Единственное, что может повлиять на ход выполнения — это исходные данные, однако при одних и тех же исходных данных, алгоритм всегда выдает один и тот же результат.
Эти три свойства присущи всем алгоритмам. Если нарушено хотя бы одно из них, перед нами уже не алгоритм. С натяжкой к обязательным свойствам можно добавить понятность для исполнителя, хотя это уже на грани фола. По большей части. это относится не к самому алгоритму, а к его записи.
«Винегрет» из свойств из того же учебника по информатике.
Необязательные свойства
Наряду с обязательными свойствами, алгоритм может обладать некоторыми частными свойствами, которые вовсе не обязательны. Начнем с массовости. Конечно, хочется, чтобы алгоритмы решали классы задач в зависимости от входных данных. Однако существуют алгоритмы, которые вообще не зависят от входных данных, например всем известный вывод на экран «Hello world». Как среди вычислимых функций существуют константные, так и среди алгоритмов существуют генераторы единственного результата.
Теперь рассмотрим широко распространенное убеждение, что алгоритмы должны обладать свойством правильности и завершаемости. Начнем с правильности. Такое свойство попросту невозможно формализовать, так как отсутствуют критерии этой правильности. Наверняка, многие из вас сталкивались с ситуацией, когда программист считает программу правильной, а заказчик нет. С завершаемостью дела обстоят интереснее. Рассмотрим термин «применимость« — алгоритм называется применимым к слову, если, получив на вход это слово, он завершается за конечное число шагов. Самое интересное то, что проблема применимости является алгоритмически неразрешимой, то есть невозможно составить алгоритм, которые определял бы по записи алгоритма и входному слову, завершится ли он за конечное число шагов. Никто не мешает вам составить программу, состоящую только из одного бесконечного цикла. И эта программа все еще будет алгоритмом.
Про зависающие программы
Программы, которые не могут зациклиться, на самом деле входят в класс примитивно-рекурсивных — подмножество частично-рекурсивного класса. Отличает их отсутствия оператора минимизации. Он то и вносит пикантности. Если вы используете «неарифметический цикл» while или рекурсию, для которых нельзя заранее определить, сколько раз они выполняться, то ваша программа сразу переходит из класса примитивно-рекурсивных в класс частично-рекурсивных.
Теперь перейдем к пресловутой последовательности шагов. Дело в том, что алгоритм может быть представлен в любой из имеющихся формальных систем (частично-рекурсивные функции, машина Тьюринга, лямбда-исчисление и т.д.). Воплощение алгоритма в виде компьютерной программы далеко не всегда будет описанием последовательности шагов. Здесь все зависит от парадигмы программирования. В императивной парадигме программисты действительно оперируют последовательностью действий. Однако существуют и другие парадигмы, такие как функциональная (привет Haskell программистам), где нету никаких действий, а лишь функции в сугубо математическом смысле, или чистая объектно-ориентированная, которая основана не на «последовательности действий», а на обмене сообщениями между абстрактными объектами.
Заключение
Иногда мир устроен несколько сложнее, чем хотелось бы. Существующие формализмы в теории алгоритмов не более чем абстрактные математические системы, наподобие геометрии Евклида или теории вероятности, тогда как понятие вычислимости, возможно, находится вне математики и является свойством нашей Вселенной наряду со скоростью света и законом всемирного тяготения. И хотя, скорее всего, нам так и не удастся ответить на вопрос, что такое алгоритмы и вычислимость, попытки найти ответ на этот вопрос оказались более ценными, чем возможный однозначный ответ.
Материал данной статьи во многом опирается на 1-ый том «Программирование: введение в профессию» А. В. Столярова. Тем, кто хочет подробнее изучить вопросы, связанные с алгоритмами и теорией вычислимости, кроме этой книги, советую Босс В «От Диофанта до Тьюринга» и трехтомник А. Шеня по математической логике и теории алгоритмов.
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.
Алгоритмы с прерыванием, бесконечные алгоритмы, которые не решаются
В предыдущих темах todid.ru мы много говорили об алгоритмах и алгоритмизации процессов.
В данной статье мы попробуем составить наглядный пример схемы действий, применительно к конкретной задаче.
Например, если попробовать описать в виде алгоритмического процесса действия мифологического Сизифа, то окажется, что за любое конечное число шагов желаемый для него результат (подъем камня на вершину скалы) недостижим в силу возникновения непреодолимых препятствий.
Задача Ахиллеса
Если попытаться построить алгоритм решения задачи, в основе которой лежит известный логический парадокс:
«За какое время Ахиллес догонит черепаху, если в каждый момент времени движется в 10 раз быстрее, чем она, то поскольку при таких условиях расстояние между «соревнующимися» будет сокращаться до бесконечности, но никогда не исчезнет, алгоритм решения задачи за конечное количество шагов не даст результата».
Деление 10 на 3
Известен пример бесконечного алгоритмического процесса, который получается при переводе неправильной дроби в десятичную.
Процесс деления 10 на 3 может продолжаться беспрепятственно до бесконечности. Значит, известный алгоритм неприменим, поскольку не позволяет получить точное значение частного за конечное число шагов. Однако если поставить задачу иначе, предусмотрев обрыв алгоритма на каком-то шаге (вычисление с заданной точностью, уточнение алгоритма) — алгоритм окажется результативным.
То же можно сказать о нем, если считать 3 (3) точным значением частного от деления 10 на 3.
Пример незавершенного алгоритма
1.1. Типичен пример, когда алгоритмический процесс безрезультатно обрывается. Пусть алгоритм состоит из следующей последовательности предписаний (они записаны ниже в виде текста п.п. 1—4):
1. Исходное данное умножить на 3.
2. К полученному результату прибавить 2.
3. Определить остаток «Х» от деления полученной суммы на 4.
4. Разделить исходные данные на «Х».
1.2. Предоставляем читателю возможность самому убедиться в том, что если исходное данное равно:
например, числу 2, «Х» оказывается равным «0» и алгоритм безрезультатно обрывается, поскольку деление оказывается невозможным и п. 4 не выполним.
Пример расчета, где К=0:
4 х 0 + 2 = 2;
2 х 3 = 6;
6 + 2 = 8;
8 / 4 = 2,0
ЦЕЛАЯ ЧАСТЬ = 2, а ОСТАТОК = 0
Таким образом, следует считать, что множество значений исходных данных для приведенного алгоритма состоит из любых вещественных чисел, исключая целые вида 4K + 2.
Как называется бесконечная работа алгоритма
Выберите ОДНО из предложенных ниже заданий: 15.1 или 15.2.
15.1 Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости, разбитой на клетки. Между соседними (по сторонам) клетками может стоять стена, через которую Робот пройти не может. У Робота есть девять команд. Четыре команды — это команды-приказы:
вверх вниз влево вправо
Ещё четыре команды — это команды проверки условий. Эти команды проверяют, свободен ли путь для Робота в каждом из четырёх возможных направлений:
сверху свободно снизу свободно слева свободно справа свободно
Эти команды можно использовать вместе с условием «если», имеющим следующий вид:
Здесь условие — одна из команд проверки условия. Последовательность команд — это одна или несколько любых команд-приказов. Например, для передвижения на одну клетку вправо, если справа нет стенки, и закрашивания клетки можно использовать такой алгоритм:
если справа свободно то
В одном условии можно использовать несколько команд проверки условий, применяя логические связки и, или, не, например:
если (справа свободно) и (не снизу свободно) то
Для повторения последовательности команд можно использовать цикл «пока», имеющий следующий вид:
Например, для движения вправо, пока это возможно, можно использовать следующий алгоритм:
нц пока справа свободно
На бесконечном поле есть горизонтальная и вертикальная стены. Правый конец горизонтальной стены соединён с верхним концом вертикальной стены. Длины стен неизвестны. В каждой стене есть ровно один проход, точное место прохода и его ширина неизвестны. Робот находится в клетке, расположенной непосредственно под горизонтальной стеной у её левого конца. На рисунке указан один из возможных способов расположения стен и Робота (Робот обозначен буквой «Р»).
Напишите для Робота алгоритм, закрашивающий все клетки, расположенные непосредственно ниже горизонтальной стены и левее вертикальной стены. Проходы должны остаться незакрашенными. Робот должен закрасить только клетки, удовлетворяющие данному условию. Например, для приведённого выше рисунка Робот должен закрасить следующие клетки (см. рисунок).
При исполнении алгоритма Робот не должен разрушиться, выполнение алгоритма должно завершиться. Конечное расположение Робота может быть произвольным. Алгоритм должен решать задачу для любого допустимого расположения стен и любого расположения и размера проходов внутри стен. Алгоритм может быть выполнен в среде формального исполнителя или записан в текстовом редакторе. Сохраните алгоритм в текстовом файле.
15.2 Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, кратное 5. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 5. Количество чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна вывести одно число — максимальное число, кратное 5.
Пример работы программы:
| Входные данные | Выходные данные |
| 3 10 25 12 | 25 |
15.1 Следующий алгоритм выполнит требуемую задачу.
Эпилог: алгоритмы, которые работают бесконечно
У каждого десятилетия свои увлекательные головоломки; и если в начале 1980-х годов бесспорное первое место среди математических развлечений занимал кубик Рубика, то “Тетрис” вызывает похожее чувство ностальгии по концу 80-х и началу 90-х годов. У кубика Рубика и “Тетриса” есть кое-что общее: математический оттенок, базирующийся на стилизованных геометрических формах, — но пожалуй, различия между ними представляют еще больший интерес.
Кубик Рубика — игра, сложность которой определяется огромным пространством поиска; к заданной перемешанной конфигурации кубика требуется применить серию операций, чтобы достичь конечной цели. С другой стороны, “Тетрис” (в его “чистой” форме) имеет куда более размытое определение успеха; вместо конкретной конечной точки вы сталкиваетесь с бесконечным потоком событий, на которые необходимо непрерывно реагировать.
Эти отличительные признаки “Тетриса” напоминают аналогичные темы, проявившиеся в недавних работах по анализу алгоритмов. Все чаще встречаются ситуации, в которых традиционные представления об алгоритмах — в начале выполнения алгоритм получает входные данные, выполняется за конечное количество шагов и выдает результат — уже неприменимы. Попробуйте представить себе маршрутизаторы в Интернете, которые передают пакеты и пытаются избежать перегрузок; или децентрализованные механизмы обмена файлами, которые копируют и распространяют контент по требованию пользователей; или средства машинного обучения, формирующие прогностические модели концепций, изменяющихся со временем; во всех этих случаях мы имеем дело с алгоритмами, практически предназначенными для бесконечного выполнения. Признаком успешного выполнения является не окончательный результат, а способность алгоритма сохранить работоспособность в постоянно изменяющейся среде, постоянно подкидывающей новые задачи. В таких ситуациях мы переходим из мира кубика Рубика в мир “Тетриса”.
Существует много разных примеров, на которых можно исследовать эту тему. В последнем разделе книги мы рассмотрим одну из самых интересных ситуаций: разработку алгоритмов для высокоскоростной коммутации пакетов в Интернете.
Задача
Пакет, перемещающийся от источника к получателю в Интернете, можно представить как маршрут обхода пути в большом графе, узлам которого соответствуют сетевые коммутаторы, а ребрам — кабели, которые связывают коммутаторы. У каждого пакета p имеется заголовок, по которому коммутатор при поступлении пакета p по входному каналу может определить выходной канал, через который p следует отправить. Таким образом, задача сетевого коммутатора — взять поток пакетов, прибывающих по входным каналам, и как можно быстрее переместить каждый пакет в конкретный выходной канал, по которому он должен быть отправлен. Насколько быстро? В средах с высокой нагрузкой пакет может поступать на каждый входной канал через несколько десятков наносекунд; если пакеты не будут передаваться на соответствующие выходные каналы со сравнимой скоростью, то трафик начнет накапливаться, что приведет к потере пакетов.
Рассмотрим пример на рис. Е.1. За один квант времени на пустой коммутатор прибывают три пакета p, q и r по входным каналам I1, I3 и I4 соответственно. Пакет p предназначен для выходного канала O1, пакет q — для канала O3, и пакет r тоже предназначен для O3. С отправкой пакета по каналу O1 проблем нет; но по каналу O3 может быть отправлен только один пакет, поэтому коммутатор должен разрешить конфликт между q и r. Как это сделать?
Рис. E.1. Коммутатор с n = 4 входными и выходными каналами. За один временной шаг прибывают пакеты p, q и r
Простейшее поведение коммутатора в такой ситуации называется чистой выходной очередью; по сути, это идеализированная картина того, что бы мы хотели видеть от коммутатора. В этой модели все пакеты, прибывающие на некотором шаге, помещаются в выходной буфер, связанный с выходным каналом, и отправляется один из пакетов из каждого выходного буфера. Ниже приведена более конкретная модель одного временного шага.
Итак, на рис. E.1 заданный временной шаг может закончиться тем, что пакеты p и q будут отправлены по своим выходным каналам, а пакет r останется в выходном буфере O3. (В дальнейшем обсуждении этого примера предполагается, что при принятии решений q отдается предпочтение перед r.) В этой модели коммутатор представляется как идеальный объект, через который пакеты беспрепятственно проходят к своему выходному буферу.
Однако на практике пакет, поступивший по входному каналу, необходимо скопировать в соответствующий выходной канал, а эта операция требует некоторых вычислений, которые блокируют входной и выходной каналы на несколько наносекунд. Итак, в действительности ограничения коммутатора создают некоторые препятствия при перемещении пакетов из входных каналов в выходные.
Самая жесткая модель этих ограничений — очереди ввода/вывода — работает следующим образом: имеется входной буфер для каждого входного канала I, а также выходной буфер для каждого выходного канала O. При поступлении пакет немедленно помещается в соответствующий входной буфер. За один временной шаг коммутатор может прочитать не более одного пакета из каждого входного буфера и записать не более одного пакета в каждый выходной буфер. Итак, в модели очередей ввода/вывода пример на рис. E.1 будет работать так: каждый из пакетов p, q и r помещается в отдельный входной буфер; коммутатор перемещает p и q в их выходные буферы, но не может переместить все три пакета, потому что для этого пришлось бы записать два пакета в выходной буфер O3. Таким образом, первый шаг завершится отправкой пакетов p и q по их выходным каналам, а пакет r остается во входном буфере I4 (вместо выходного буфера O3).
Выбор перемещаемого паросочетания пока остается не определенным; важность этого момента станет ясна позднее.
Итак, при использовании очередей ввода/вывода коммутатор создает некоторое “трение” на пути перемещения пакетов, причем это объективно наблюдаемое явление: если рассматривать коммутатор как “черный ящик” и просто наблюдать за последовательностью отправок по выходным каналам, можно заметить различия между чистой выходной очередью и очередями ввода/вывода. Рассмотрим пример, в котором первый шаг в точности повторяет рис. Е.1, а на втором шаге прибывает один пакет s типа (I4, O4). При использовании чистой выходной очереди пакеты pи q отправятся на первом шаге, а r и s — на втором. С другой стороны, при использовании очередей ввода/вывода происходит последовательность событий, изображенная на рис. Е.2: в конце первого шага r по-прежнему находится во входном буфере I4, а в конце второго шага один из пакетов r или s также остается во входном буфере I4, ожидая отправки. Конфликт между r и sназывается блокировкой очереди; из-за него коммутатор с очередями ввода/вывода по своим характеристикам задержки уступает чистой выходной очереди.
Рис. E.2. Двухшаговый процесс, приводящий к блокировке очереди
Моделирование чистой выходной очереди
Поведение чистой выходной очереди было бы удобным, но из сказанного выше понятно, что препятствует реализации коммутатора с таким поведением: за один временной шаг (продолжительностью всего десятки наносекунд) переместить пакеты из одного из n входных каналов в общий выходной буфер в общем случае не удастся.
Но что, если взять коммутатор с очередями ввода/вывода и ускорить его работу, перемещая несколько сочетаний за шаг вместо одного? Возможно ли смоделировать коммутатор, использующий чистую выходную очередь? Под этим термином здесь понимается, что последовательность отправок по выходным каналам (при которой коммутатор рассматривается как “черный ящик”) должна быть одинаковой для реализации поведения чистой выходной очереди и ускоренного алгоритма очередей ввода/вывода.
Нетрудно понять, что ускорения в n раз будет достаточно: если мы сможем перемещать n сочетаний на каждом шаге, то даже если все прибывающие пакеты должны попасть в один выходной буфер, мы смогли бы переместить их все за один шаг. Но ускорение в n раз совершенно нереально; и если рассматривать происходящее как худший случай, появляется неприятная мысль о том, что без ускорения в n раз не обойтись, — в конце концов, что делать, если все прибывающие пакеты действительно должны быть направлены в один выходной буфер?
В этом разделе будет показано, что хватит гораздо более умеренного ускорения. Мы опишем поразительный результат, который получили Чуан, Гоэл, Маккеун и Прабхакар (Chuang, Goel, McKeown, Prabhakar, 1999), — он показывает, что коммутатор, использующий очереди ввода/вывода с ускорением 2, может моделировать коммутатор с чистой выходной очередью. На уровне здравого смысла этот результат использует тот факт, что внутреннее поведение коммутатора не обязано напоминать поведение чистой выходной очереди, если последовательность отправок пакетов с выходных каналов остается неизменной. (Следовательно, продолжая пример из предыдущего абзаца, не обязательно перемещать все n входных пакетов в общий выходной буфер за один шаг; для этого можно выделить больше времени, потому что их отправки по общему выходному каналу все равно будут распределены по более длинному периоду времени.)
Разработка алгоритма
Просто для ясности приведем модель для ускорения 2.
Чтобы доказать, что эта модель способна имитировать чистую выходную очередь, необходимо разрешить важный, недостаточно определенный момент: какие паросочетания должны перемещаться на каждом шаге? Ответ на этот вопрос образует основу результата, и мы придем к нему через серию промежуточных шагов. Начнем с одного простого наблюдения: если пакет типа (I, O) является частью паросочетания, выбранного коммутатором, то коммутатор переместит пакет этого типа с самым ранним временем отправки.
Организация входных и выходных буферов
Чтобы решить, какие два паросочетания коммутатор должен переместить на заданном шаге, необходимо определить некоторые характеристики, определяющие текущее состояние коммутатора относительно чистой выходной очереди. Для начала для пакета p определяется его время отправки TL(p), равное временному шагу, на котором он был бы отправлен по выходному каналу коммутатора при использовании чистой выходной очереди. Мы стремимся к тому, чтобы каждый пакет p отправлялся из коммутатора (с ускоренными очередями ввода/вывода) ровно на шаге TL(p).
На концептуальном уровне каждый входной буфер представляет собой упорядоченный список; при этом сохраняется возможность вставки прибывающих пакетов в середину порядка, а также перемещения пакета в выходной буфер даже тогда, когда он еще не находится в начале очереди. Несмотря на это, линейное упорядочение буфера образует полезную метрику прогресса. С другой стороны, выходные буферы упорядочивать не нужно; когда приходит время отправки пакета, он просто покидает буфер. Конфигурация напоминает терминал аэропорта: входные буферы соответствуют стойкам регистрации, выходные — залам ожидания, а внутренняя реализация коммутатора — сильно загруженному контрольному пункту службы безопасности. Основное напряжение приходится на входные буферы: если не успеть к началу очереди до завершения регистрации, то вы можете опоздать на самолет; к счастью, служащие аэропорта могут извлечь вас из середины очереди и провести через контрольный пункт в ускоренном темпе. Напротив, в выходных буферах можно расслабиться: пассажиры спокойно сидят, пока не будет объявлена посадка на их рейс, после чего просто отправляются на самолет. Главное — преодолеть “затор” в середине, чтобы пассажиры успели к отлету.
Итак, наш план: паросочетания будут передаваться по коммутатору так, чтобы постоянно сохранялись следующие два свойства:
(i) Slack(p) ≥ 0 для всех необработанных пакетов р;
(ii) На любом шаге, начинающемся с IC(p) = OC(p) = 0, пакет p будет перемещаться в свой выходной буфер в первом паросочетании.
Сначала нужно убедиться в том, что сохранения этих двух свойств достаточно.
(E.1) Если свойства (i) и (ii) выполняются для всех необработанных пакетов во все моменты времени, то каждый пакет p будет отправлен в свое положенное время TL(p).
Как выясняется, свойство (ii) гарантируется достаточно легко (и оно естественно выполняется в приведенном ниже решении), поэтому мы сосредоточимся на непростой задаче выбора паросочетаний для поддержания свойства (i).
Перемещение паросочетания через коммутатор
Когда пакет p только прибывает во входной канал, он вставляется как можно ближе к концу входного буфера (вероятно, где-то в середине) в соответствии с требованием Slack(p) ≥ 0. Это гарантирует, что свойство (i) будет изначально выполняться для p.
Чтобы поддерживать неотрицательность Slack с течением времени, необходимо побеспокоиться о компенсации событий, приводящих к убыванию Slack(p). Вернемся к описанию одного временного шага и подумаем, как происходит такое убывание.
Рассмотрим пакет p, остающийся необработанным в начале временного шага. В фазе прибытия IC(p) может увеличиться на 1, если прибывающий пакет помещается во входной буфер передp. Это приведет к уменьшению Slack(p) на 1. В фазе отправки этого шага OC(p) может уменьшиться на 1, так как пакет с более ранним временем отправки уже не будет находиться в выходном буфере. Это тоже приведет к уменьшению Slack(p) на 1. Итак, Slack(p) теоретически может уменьшиться на 1 в каждой из фаз прибытия и отправки. Соответственно выполнение свойства (i) будет обеспечено, если мы сможем гарантировать, что Slack(p) увеличивается по меньшей мере на 1 при каждом перемещении паросочетания через коммутатор. Как этого добиться?
Если перемещаемое паросочетание включает пакет из I[p], находящийся перед р, то IС(р) уменьшается, а следовательно, Slack(p) увеличится. Если паросочетание включает пакет, предназначенный для O[p], но имеющий более раннее время отправки, чем р, то OC(p) и Slack(p) возрастут. Итак, проблема возникает только в том случае, если не происходит ни одно из этих событий. На рис. E.3 приведено схематичное изображение такой ситуации. Предположим, пакет x перемещается из I[р] даже в том случае, если он находится ближе к концу очереди, а пакет у перемещается в O[p], хотя он имеет более позднее время отправки. В такой ситуации буферы I[p] и O[p] работают “некорректно”: для I[p] было бы лучше отправить пакет, находящийся ближе к началу очереди (такой, как p), а для O[p] было бы лучше получить пакет с более ранним временем отправки (такой, как p). В сочетании два буфера образуют некий аналог неустойчивости из задачи об устойчивом паросочетании.
Мы можем этот принцип выразить точно — и он станет ключом для завершения алгоритма. Допустим, для выходного буфера O входной буфер I является предпочтительным перед /’, если самое раннее время отправки среди пакетов типа (I, O) меньше самого раннего времени отправки между пакетами типа (I’, O). (Иначе говоря, если у буфера I существует более срочная потребность отправить что-то в буфер O.) Кроме того, для входного буфера I выходной буфер O является предпочтительным перед выходным буфером O’, если ближайший к началу пакет типа (I, O) опережает ближайший к началу пакет типа (I, O’) в упорядочении I. Для каждого буфера по этим правилам строится список предпочтений; и если пакетов типа (I, O) вообще нет, то I и Oпомещаются в конец списка предпочтений друг друга, с произвольной разбивкой связей. Наконец, алгоритм определяет устойчивое паросочетание M с учетом этих списков предпочтений, и коммутатор перемещает это паросочетание M.
Рис. E.3. Выбор перемещаемого паросочетания
Анализ алгоритма
Следующее утверждение показывает, что выбор устойчивого паросочетания действительно дает алгоритм с нужными гарантиями быстродействия.
(E.2) Предположим, коммутатор всегда перемещает устойчивое паросочетание M в отношении списков предпочтений, определенных выше. (И для каждого типа (I, O), содержащегося в M, выбирается пакет этого типа с самым ранним временем отправки.) Тогда для всех необработанных пакетов p при перемещении паросочетания M значение Slack(p) увеличивается минимум на 1.
Доказательство. Рассмотрим любой необработанный пакет р. Продолжая предшествующее обсуждение, предположим, что в составе паросочетания M не перемещается никакой пакет, опережающий р в I[p], и никакой пакет, предназначенный для O[p], с более ранним временем отправки. Итак, пара (I[p], O[p]) не принадлежит M; предположим, что пары (I’, O[p]) и (I[p], O’) принадлежат M.
Пакет p имеет более раннее время отправки, чем любой пакет типа (I’, O[p]), и опережает все пакеты типа (I[p], O’) в упорядочении I[p]. Отсюда следует, что для I[p] буфер O[p] является предпочтительным перед O’, и для O[p] буфер I[p] является предпочтительным перед I’. Следовательно, пара (I[p], O[p]) образует неустойчивость, что противоречит предположению об устойчивости M. ■
Следовательно, перемещая устойчивое паросочетание на каждом шаге, коммутатор поддерживает свойство Slack(p) ≥ 0 для всех пакетов p; следовательно, в соответствии с (E.1) мы доказали следующее:
(E.3) Перемещая два устойчивых паросочетания на каждом временном шаге, в соответствии с только что определенными предпочтениями, коммутатор может имитировать поведение чистой выходной очереди.
Получается, алгоритм совершенно неожиданно встречается в теме, с которой начиналась книга, — но вместо пар из мужчин и женщин или работодателей и работников здесь формируются пары входных и выходных каналов в высокопроизводительном интернет-маршрутизаторе.
Мы всего лишь мельком затронули тему алгоритмов, работающих бесконечно в условиях бесконечного потока новых событий. В этой интересной области полно нерешенных проблем и открытых направлений. Но этой темой мы займемся как-нибудь в другой раз и в другой книге, а эта книга подошла к концу.
Библиотека образовательных материалов для студентов, учителей, учеников и их родителей.
Наш сайт не претендует на авторство размещенных материалов. Мы только конвертируем в удобный формат материалы из сети Интернет, которые находятся в открытом доступе и присланные нашими посетителями.
Если вы являетесь обладателем авторского права на любой размещенный у нас материал и намерены удалить его или получить ссылки на место коммерческого размещения материалов, обратитесь для согласования к администратору сайта.
Разрешается копировать материалы с обязательной гипертекстовой ссылкой на сайт, будьте благодарными мы затратили много усилий чтобы привести информацию в удобный вид.
© 2014-2021 Все права на дизайн сайта принадлежат С.Є.А.